Purging and reinstalling worked. There are a couple of things I can think of as possible culprits:

1. I added the connection during installation.
2. The connection was added automatically as a result of my using the applet and selecting my wireless AP from the list of available ones. After purging I went through system settings and manually added the connection first.

That being said, one shouldn't have to be so careful. Further, I find it troubling that at no point in modifying the system network settings was I ever asked for a password. Users should be asked to authenticate when writing files to an /etc subdirectory, IMHO.

Anyway it works now. Horray. I'm still interested in researching into the matter because I had the same problem on Debian testing (and even Debian Developers were scratching their heads). I still believe there's some funkiness with N-M, permissions, and or keyrings.

Thanks for the help!