I finally figured out how to import contacts into Gmail. I was right about how the new version of Gmail exports and imports incorrectly. Not only are the CSV files from the old version of Gmail incompatible, but Gmail fails to import a file generated by the new version of Gmail.
What I had to do instead was go back to the old version and do all the importing there. The main difference between the old format and the new format was the separator used; the new format uses the semicolon as the separator between different entries in the same field (say, multiple home email addresses), while the old version uses the string ' ::: '. It was an easy thing for me to do a search and replace to convert my own CSV file to Gmail format.
The funny thing is that I don't think my file works that well for the old version either. If you look at an imported contact in the old version, some of the information is moved to the notes section, meaning Gmail doesn't really know what to do with it. Switching to the new version, however, the contact is displayed correctly, with separate email addresses and IM's and everything.
So, after figuring this out, I have to agree with a lot of commentators on the web that the new version of Gmail still has a number of bugs. I still use the new version as the default, but I'm also prepared for some things to not work as well as in the old one.