Do you store only names & numbers, or more than that (birthdays, addresses, notes, etc.)?
There used to be a very good 3rd-party Nokia suite out there ... it's been years since I tried it, though, so it may no longer be around. Depending on the number of contacts, it may be well worth the time investment to go looking for a mass export solution.
By the way, my experience with the GMail contacts importer is that, whichever import format you choose, only about 80% of the fields will get imported correctly -- you will have quite a bit of manual typing ahead of you.