This has happened twice, with two different Android recipients.
Both have been Android phones since inception - read: never had iMessage, so Apple shouldn't be confused about iMessage.
Anyway, we've had recent failures sending pics to Android phones we've sent pics before. We get:
Cannot Send Message iMessage needs to be enabled to send this message
iMessage is enabled.
So, I tried a phone bounce, disabling/re-enabling iMessages, disabling/re-enabling MMS. Disabling/re-enabling WiFi (TMobile, allows WiFi as an SMS/MMS transport). No good. A simple text message worked tho. just no pics
EDIT: versions would be nice. iOS 8.3. iPhone 6.
UPDATE: I was able to send by sending to a new MMS group; the intended recipient and an iMessage account.