When this has happened with other handsets in the past, it's generally because the recipient number has been used with iMessage in the past and the current iPhone users have imessage active.
You'll either need to put your SIM in to an iPhone, turn off imessage, or get your iPhone using friends to turn it off at their end.