OK, figured out it myself. We had the Uploadify inside of jQuery dialog, and since jQuery UI dialog is instantiated on-the-fly by jQuery it does not sit in DOM properly so it crashes. As soon as we placed Uploadify in plain and simple div it started working properly on all browsers. So people, my advice to you is: use that Firebug as much as you can, it is your best friend in the dark world out there.

Now the only problem we have is a dreaded I/O #2038 error. This can apparently mean anything but it is amazing that nobody came with proper solution for IIS, I could only see some people that had it working under Apache. If anybody has any suggestions on how to handle this error in IIS 7 with default app pool and 'Forms' authentication, I would be very much grateful.

to gummikalli:
it works after using your method.
I registered just to say thanks to you!!!!!!
really strongly!

After all my excitement, there was yet one more problem.
After closing the dialog, when opening it again, the same problem returned.
I guess every time the dialog is opened it rebuilds the DOM in the way DragonB explained.
This creates the issue where IE cannot make the function calls from the flash object.
To resolve that issue, I only defined the div container for the button in the original code for my dialog. I also do not call the uploadify init in my onload, only the dialog init.
Then, in your code that opens the popup, first assign the html for your upload button inside your div, then call the uploadify init. Then you can open your dialog with a fresh version of the uploadify that IE can recognize in the dom.

Example of HTML page:

<input type="button" value="Open Photo Dialog" onclick="DialogOpen()" />
....
<div id="dialogUpload">
...
<div id="uploadButtonContainer"></div>
...
</div>


Example of js file:

// Open Dialog Window
function DialogOpen() {
var buttonText = '<input type="button" id="uploadButton" value="Choose Photos" />';
$("#uploadButtonContainer").html(buttonText);
$("#uploadButton").uploadify({...});
$("#dialogUpload").dialog("open");
}

// onload events
$(function () {
$("#dialogUpload").dialog({....});
}


That seemed to do the trick for me. Otherwise you may want to open the dialog first, then apply the html and uploadify. Also, remember when closing the dialog you will want to uploadifyClearQueue, since the new uploadify button doesnt know about the old items. Otherwise you can put your entire html for the popup on each load to prevent the old queue from showing.