I know my account was hacked and used to spam all of my contact list.  They even added a message in my signature line about going to a certain site I had never been to before.  Its an old account that I only use for a few things, but one of my friends told me they'd been receiving weird messages from that account.  I changed my password and actually deleted my entire contact list to hopefully avoid the problem in the future.

After doing all that (and at that point I could still send a message), now I'm not allowed to send messages from my account.  Is there anything I can do?

It's possible that you were victimized by the latest Malware attack. Check out this Solution article for more info about it and for ways on how you can make your account and computer more secure:

http://windowslivehelp.com/solutions/safety/archive/2009/04/29/recent-reports-of-account-hijacks.aspx

As a safety measure, make sure the computer is updated. To get the latest security updates, visit our PC Safety line link:

http://www.microsoft.com/protect/default.mspx

Now, about your sending issue, please post your e-mail address so I can validate if the account has been genuinely blocked or if it’s a false alert.