Hi I'm having this exact problem and have done some debugging:

When making a new SMS there's three steps
1: you first select recipients
2: then you write the body of the SMS
3: you schedule the SMS

Between step two and three the table civicrm_mailing_recipients correctly gets filled with email_id set to null and phone_id set with the id of the contacts phonenr. This gets done in the function getRecipients in CRM/Mailing/BAO/Mailing.php, and the phone_id's get set because $mode is set to "sms".
But between step two and three this function is called again (don't know why?) and $mode is now empty, and the email_id is set instead and phone_id is set to null. This results in an empty result from an sql-call in the function deliver in CRM/Mailing/Bao/MailingJob.php, and thus there's no one to send to.

I don't know why this second call is made or why $mode is empty the second time around.

I know this is not a complete answer, but it's a very good clue to whats wrong, and I don't have enough points to comment, so here it is. Lets figure out exactly whats wrong, and file an issue with a patch :)