Try gtkpod; Katherine's using it with her Nano and it handles re-encoding from other formats just fine.
J.
Seconded.
I worked on the conversion scripts to allow conversion from FLAC -> M4A on-the-fly. :)
My collection is stored in FLAC and I use gtkpod to sync it all the time with my 2nd gen Nano - it works gr8.
Peter.