iPods work with physical Hard Drive limits, not by an actual number of songs. The 1000 song estimate is an estimate of each song being recorded at 128kbps mp3 and each song being 4 minutes long. What is most likely the case is that you have your songs encoded higher than that, which takes up more hard drive space than the estimate, giving you less songs at full
capacity.