I experience the same problem... i recently formatted and reinstalled three computers (2 desktops, 1 laptop) and on all three i downloaded the latest version of Live Messenger. Onfortunately, all three computers have this same problem (doesn't matter wich user is logged in) of blocking new contacts after adding them. That is, the new concact appears with a red line through his status-icon. When I right click the contact's name, i can only choose: "block"... so somehow Live Messenger knows I did not really block it. Choosing block and immediately after that unblocking the contact solves the problem, but that's not a solution but a work around
any ideas or official Live Messenger announcements known?
