The messaging system is still there - I contacted someone yesterday, off-board, using the username link on one of the message boards.
Also, if you have previously contacted someone and have that mail in your message box, you can contact from that username link.
Agreed that it seems broken from the username link in a tree. For me, it is hit and miss from the Member Directory. I can locate some people by username but not others.
Edit: Midday US Eastern time it seems to be working better. I have only tested a few, but I have been able to click through from a profile name in several trees.