Thank you for writing it here, it feels nice that somebody else is having this very same issue getting only the Black preview image at Facebook. They are such UGLY!
I have the same problem, it might be an server/facebook combo issue or a plugin issue. Here is a list of my Plugins. Is any of them matching your Plugins, Nick2012? (I already tested to turn on/off the cache plugin, that didn't seem to help)
Google XML Sitemaps
Peetra's Custom Made Editor Addons
Really simple Facebook Twitter share buttons
WP Super Cache
WP Video Lightbox
I also recently have had "PagePressApp.com Auto Wall Post" on my WP blog/FB Page, it was never working properly and when the black pic-issue turned up about 4 days ago I turned the Auto Wall post off.
As a temp fix I was thinking of replacing the black pic with something more proper for my site. But I haven't yet found it to test this. Anybody knows where it is located? It is not the photo located at facebook that you posted, nick2012. The image is somewhere in our own directories, but WHERE?, it is the same pic used for generating previews when somebody have made a faulty URL in comment form's and you can see it inside your Admin Panel when hoovering over a faulty url in a comment.
Another temp fix that I have made for one important post (that should be shared/liked at least 100 times at Facebook) was that I made a static html-file before posting my blog post. I shared the link to the static file at Facebook myself making Facebook cache my desired Pic from that URL. I then deleted the static file and renamed my post's url to what I already had sent to Facebook. Problem solved for that particular post at least.
Facebook cache's preview pics quite long, about 4 days I have noticed. So the workaround I made is fine for important posts, as the news value for me is over in 7 days anyway. But I wasn't really signing up for making static html files manually when starting to use WordPress, LOLs, so my workaround isn't desirable.