Ah, the plot thickens:
Turns out the plugin was working fine all along - it was my method of testing that was to blame:
On my test site I created a new post, and after publication I could push the post to Facebook with no problems. However on my client's site I tried to push a post to Facebook that had already been published before we installed he plugin. This doesn't seem to work.
But publishing a new post on the site and then pushing it to Facebook works a treat - my client only found this out by chance. Now we know!
If any of you guys are having trouble try the new post method first - worked for me ;-)