Actually, I have run into a similar problem before. I think my solution was to fadeOut, then wait until the image was fully loaded, then fadeIn. "Waiting until fully loaded" meant that I created an image object, set the src property to the required image url, then checked the .complete property in case the image was already in cache. If .complete was true then set the actual displayed image's src to that of my image object, otherwise I attach this part of the process to the image object's load event.
I have dug out an ancient plugin I created at the time which does everything I just blathered on about. Please forgive the sometimes bizarre code at the start of that plugin - not sure what I was thinking there. You may get some clues from the last half of it though. http://users.tpg.com.au/j_birch/plugins/changeImg/ Actually, if you disable the cache on my test page you can still see the effect you describe. Maybe that is a clue - surely it is to do with the image not being cached in advance enough. If you enable the cache but clear it before viewing my test page though, it works fine. Hope some of this helps you figure it out. Joel Birch.
