I would say that first it depends on you ears, and in second place of the system (speakers mostly, in that I agree with KW, as even affordable electronic are nowadys excellent). If you work in a very loud place, used to go to discos with a noise level of 110 dBA 4 times a week, I think a 56 kbs mp3 would do..
, you will not hear any difference to better formats.
When getting the iPod I made several hearing tests with different formats. Beginning with the fact, that all formats except true analog recordings are lossy formats (best quality recording I have is a Japan vinyl from The Concert for Bangla Desh from George Harrison), my personal preferences based on my genes and earing capabilities history are as follow:
1. AACplus 320 kbs (unfortunatelly the iPod does not digest it)
2. AAC 320 kbs (more brilliant than the lower AAC codings)
3. MP3 320 kbs
And the lower rates follow.
I have to emphasis here that I never tried flac or ogg, although there is a radio on the net which uses orgg at VBR (aprox 80 kbs) with an excellent sound