If you have Media Player 10, it can rename your media based on the ID3 tags. If you don't have tag information either, they you're out of luck, you'll have to edit the tags and rename the files manually.
As far as I know, there is no such service that can tell what a song is and rename it. But there are many programs that can read ID tags of your MP3 files and rename the file itself using that info. Look in the Media Player options there is a section for renaming media, then read the help and info files before you have it rename stuff.