Disabling CABAC will allow you to sync your files with your iPod. Tried this on an 80GB Classic (5.5G) and it worked flawlessly, even with CUDA.
Ideal settings on a Classic:
Resolution: 320x240 (no need to encode at a higher resolution since this is what the ipod displays at)
H.264 (Use CUDA if you are able to)
Audio: Nero AAC
I can provide any additional information as it is requested.