I believe the user (the users who you are trying to send a message to) needs to have the correct privacy settings setup as well. If they have it set to a specific group (say friends) and you are not their friend, they you wont see the button on their profile. If they have it set to public, then anyone can see the button and see the Simple Instant Message box and the Video message icon.
BTW, the Privacy settings are under the dashboard little icon.
I'm no D7 pro, but I found this out while playing with the software as two different users.
Hope this helps.
Regards,