Ugh, this was because my facebook project was not in a published state (I'm developing it now), and the user I was trying to send the messages to was not marked as a developer or tester of my project.
What an epic waste of time - would be nice if the facebook api could return a simple error message giving you a hint.