It turns out this was just the Android SDK's way of wishing me a happy anniversary as an Android developer: My signing certificate had expired.
[Aside for anyone who has stayed blissfully ignorant of the signing process] All Android applications have to be signed with a certificate to identify the creator. By default, your applications are signed with a special Debug Certificate which can't be used to distribute your application. This certificate is automatically created when you first compile an application, and it expires after one year. Once it expires, you need to recreate it. [End of aside]
You can find an explanation of it at the Android Developer site. I'll save you some trouble and quote the easy fix for the problem here:
To fix this problem, simply delete thedebug.keystorefile. The default storage location for AVDs is in~/.android/on OS X and Linux, inC:\Documents and Settings\<user>\.android\on Windows XP, and inC:\Users\<user>\.android\on Windows Vista and Windows 7.
The other problem is you'll have to reinstall apps you installed using the old certificate. And while you're at it, this would be a good time to read the whole page on signing and familiarise yourself with the concept. You know, just in case you hadn't bothered to learn about it until now.