Do you have a USB packet sniffer? I fixed a problem with one of the ColdFire bootloaders where it was not responding to a particular (GetConfiguration) message that is sent by Mac OS X but not Windows. You should be able to see the exact point where the failure starts.
I'm very surprised that the responses come out of order. That might require some serious code review. Then again, it could be that the problems only start after an initial failed response causes havoc with a state machine.
I have a hunch that Windows 7 and 8 have started using more of the USB standard command messages. Technically, the requests are legal, but the ColdFire firmware does not fully implement all the parts of the USB standard. It may be a simple matter of implementing one or more additional USB commands and everything will fall into place. In my experience, the bootloader at least took many shortcuts, not implementing any more than the most basic commands. It seems possible that the code you have skipped a few commands, or perhaps USB has added some new commands that are confusing the old code.