Whatsapp works based on phone numbers and has nothing to do with the device you're using. First, make sure that you and your friend have each other's numbers saved on their contact list (that's where Whatsapp looks for contact information). Done?
Now check that neither has the other phone number in their block list, especially if this is not a new number; it may have been used in Whatsapp before.
OK, now go into Whatsapp, go to the contact list (where you start a new chat) and hit the Menu button and select "Refresh". This will force Whatsapp to repopulate your list with new contacts. Is he there now?
If not, try adding the country code for your friend's phone number (for instance, if in the US, add '+1'). Refresh the contact list again? Is he there now?
If not, try adding an additional '1' after the country code and before the phone number (for international cellphones, this sometimes helps). Refresh contact list again. Is he now in your list?