Is there an open source service that I can call from a program, where it passes information about a un-tagged mp3, and it responds with details about the song(e.g. artist, album, track, etc.)? If not, is there an alternative I can use to identify songs?
MusicBrainz is one that works pretty well. It uses an "acoustic fingerprint" to look up potential matches.