I don't know if this helps, but I had an ipod nano, 4gb, that wouldn't play songs over 160kps. I have no idea if there is a limit in kps the ipods can handle, but the good news is I upgraded to an ipod nano 8gb and so far everything plays. Try taking your ipod to an Apple retail store. I'll bet they can help you.
Good luck.