Hmm... it verified for me using bitcoin-qt.  I'll have to check it out when I get home.

Should I have just signed the address?  I signed the entire message using the public/private key pair.  This is my first time using the sign message function.