Alright I think I found the reason for the problems I was having earlier with some albums being sorted by various artist on my new iPod even though I have them organized by Artist in my iTunes library.
I checked my iTunes media folder, and some albums are sorted under the Compilation folder instead of the corresponding artist folder. I tried moving an artist's album from the compilation folder into the corresponding artist folder but that didn't seem to do the trick.
Any suggestions?
I think reimporting the albums will solve this problem but I want to do that only as a last resort.