SOLVED
Firstly, just to confirm that the correct way to do this is:
$('#file_upload').uploadify('settings','formData', { 'myfield': 'myvalue' });
Secondly, the reason it was failing in my case was because the swf object that handles the uploading was in a tab that was not yet visible, thus disconnecting it from the Javascript. For this reason, you can change other settings when its not visible but not formData as that is set directly on the swf object.
I hope this helps someone else as much as it would have helped me! :)