You might need to edit the tags in your original mp3s. I'm assuming these are ripped CDs, since anything bought from the iTunes store should have proper tags.
The best program I have found for doing this is Tagscanner. It's free, and works a treat. Only trouble is its a bit complex. Google "tagscanner" and accept the first site on the list. It's Russian, but don't let that bother you. The site and program are all in English.
Get rid of everything from iTunes, except music that you have bought from the iTunes store. Ditto for your iDevices.
Once you have repaired your tags, you can chuck everything back into iTunes and sync, and with a bit of luck, everything will be working.
I've had some iTunes disasters when I was too lazy to tag music as I ripped it, so I know how frustrating it can be to have a load of unknown tracks by unknown artists.
Hope this helps.