I'm not familiar with using sms_client, and since I'm seeing you're from the UK, I don't know how this will work (I don't know how cell carriers operate outside the US).
I've just been e-mailing notifications to my cell phone. Carriers in the US associate your phone number with a unique e-mail address containing your phone number, hosted on the carrier's domain. For example, a Cingular cell phone's e-mail address would be XXXYYYZZZZ@mobile.mycingular.com. I can send messages to that address from any email service that I've tried, and I receive the e-mails just as if they're SMS messages. I don't know if that's how things work with carriers in the UK, though.
Anywhos, I've just been modifying the default "notify-by-email" command and included my mobile e-mail there, and I've been getting notifications whenever there's an issue. Using the Unix mail command works fine, but not when that printf string is piped to it. So here's what my command looks like:
Notify My cell - service problem
command_line /bin/mail -s "Nagios-02: $SERVICEDESC$ on $HOSTALIAS$ is $SERVICESTATE$!" $CONTACTEMAIL$
I just had to make sure to define another contact whose e-mail was my mobile e-mail. You might decide this is more trouble than it's worth, and it might not work in the UK, but I thought I'd try anyways 'cause I don't know much about sms_client.
Weird that you're getting that timeout error in Nagios and not from command-line, though...