What happens is, the iPhone attempts to send the SMS to the ex-iPhone user as an iMessage -- just like it always did before the recipient switched devices. But since Android doesn't support iMessage, the text ultimately fails.
Simple, if naive solution:
Complicated, if realistic solution:
According to a tipster in Apple's support forums, this should resolve the issue entirely. Unfortunately, this is just one of several iMessage related bugs we've been tracking lately. New service or not, Apple needs to get on top of this so users don't have to go through steps they ought not have to go through.