I have the same issue, struggling with a lot of Bluetooth problems at the moment. I also have a MW600!
I can get it to pair with the MW600 if I turn WiFi off. After pairing it seems to work fine with WiFi back on.
With various power cycles, entering and leaving flight mode etc. I can get it to see some devices. Can't get it to pair with my car kit though no matter what I do, and that's the only thing I really want to pair it with.
It seems to be a common issue with Samsung Omnia 7s and Focuses. There is a blog post that google finds where a guy took his phone back and swapped it for another one, which then worked with all the devices his original didn't. One of the commentors then declared that upgrading the firmware to JK1 also sorted the issue. I promptly did this, voiding any chance I had of taking the device back to get a new one. It didn't work, so I'm stuck. The commentor has since come back and said it didn't fix the issue. Thanks for that