Are you sure the contact is using an iDevice?
iMessage is only usable between iPads, iPhones and iPod touch. If you are attempting to send to a cellphone other than an iPhone, the iPad cannot send the message. If you send a message from an iPhone to a nonApple cellphone, it will simply go as an SMS.