If you downgraded to an Android device without first telling iMessage that your phone number was no longer on the iMessage network, then it would fail. This is unrelated to SMS fallback on an iPhone sending iMessages.