So, since you made the new account, you're not able to add any contacts on either your old or new account because it says they're both full?
Have you tried adding contacts on a web messenger such as eBuddy or on another computer?
If you have and find it's just your computer having the problem, try deleting these temporary files/folders related to Messenger:
C:\Users\
your_username\AppData\Roaming\Microsoft\MSN Messenger\
C:\Users\
your_username\AppData\Roaming\Microsoft\Windows Live Call\
C:\Users\
your_username\AppData\Roaming\Microsoft\Windows Messenger\
C:\Users\
your_username\AppData\Local\Microsoft\Windows Live Contacts\
* C:\Users\
your_username\AppData\Local\Microsoft\Messenger\
C:\Users\
your_username\AppData\Local\Temp\MessengerCache\
C:\Users\
your_username\Contacts\
* NOTE: This folder contains your custom emoticons, display pics, backgrounds, etc. so you may want to backup before deleting.
The above file locations are for Windows Vista or 7. For more info or locations for XP, see
CookieRevised's reply to Windows Live Messenger BIG PROBLEM!.
You should replace the letter C with the letter of your hard drive and your_username with the name of your Windows account.
Alternatively,
CCleaner deletes some of these temporary files/folders when you run its cleaner, may be worth a try.
/ 
