Just ask your friend to delete you (not block you) and delete you from hotmail as well. Do the same (check your hotmail contacts). And now add him back and see what happens. Or ask him to give you his Windows Live Profile link. You should be able to add him from there.
