After two weeks of frustration, EA support tells me that someone else is using my key, so too bad for me. (Idiots. Pirates use my key, and I can't? DRM sucks...)

So I took Spore back to Wal-Mart and exchanged it.

How do I enter the new key without losing all of my offline-game data that I've made? I'm on a Mac...

http://forum.spore.com/jforum/posts/list/4013.page

Awesome! By putting together various responses I was able to re-enter my license key. For clarity, here's the steps:

To re-enter your license key on a Mac (quit Spore first):

1) Delete the file ~/Library/Preferences/SPORE Preferences/system.reg
2) Delete the file ~/Library/Preferences/SPORE Preferences/user.reg
3) Delete the folder ~/Library/Preferences/SPORE Preferences/p_drive/User/Application Data/SecuROM

"~" means "/Users/(your user name)/"