Depends on what you want to do with it.
I have a little more than 30 gig of music so my old 20 gig without photo and video was already to small one should think.
No it wasn't since I do not feel the need to store all my music on it. As a matter of fact, I use it very often in my car with all the music on it in shuffle mode. Imagine a random jukebox of 4000 songs selected on most favourite, recently imported and recently played ... When I attach that iPod to my powerbook, it loads the songs and it forgets which playlist was playing. So when I'm in a hurry or when I'm lousy (most of the time
) I just pop in my iPod in my car adapter and drive away. Accessing the menu's when driving is a bad idea unless you are driving a 50 mile long straight highway in the desert.
And yes, it was much to small. Along with my new 80 gig iPod I ordered a camera connector so I have plenty of space to empty my memory cards when I'm on the road. There are also a bunch of video podcast loaded on it and perhaps when apple brings the videostore to belgium I will by one of my favourite movies. I also think to copy some crucial files to it as an extra backup.