As a test, we uninstalled the latest versions of Flash and FF locally and were able to use the flash uploader with FF12 and Flashplayer 220.127.116.11 (3rd May). Updated to the latest versions again and the problem returns. This does not effect IE or Chrome.
We have disabled the flash uploader for the time being. Has anyone else had a similar experience?