No, they are most definitely wrong. The 256 colour limit of GIF files is a common misconception.
Here is a 256 colour GIF image:
And here is a corresponding 32697 colour GIF:
The reason GIF files with more than 256 colours aren't used is due to the shear size of the files. The 256 colour image above is 53 kB, whereas the 32697 colour one is 180 kB. The equivalent PNG file for example is only a mere 13 kB. You are generally better of using a low compression JPEG than a high colour GIF, the loss in quality is usually worth it for the corresponding decrease in image quality. Although obviously a PNG is the best option to use as long as you don't require alpha level transparency.
These larger GIF files also tend to render oddly/slowly in browsers.