I saw your message as a result of a Google search while I was trying to find the solution to exactly the same problem I was having.
I just got this Nokia 6600 the other day and bought a Bluetooth adapter today. And I could get the PC and phone to pair, but not to connect - with the message that the PC didn't support the Bluetooth Handsfree Profile.
Here's what I did in the couple of hours since I saw your message - and now it is working.
1. I had assumed that the message was telling me the Bluetooth adapter was not able to support the required profile. However, your comment that you'd had it working but were now having problems made me think.
2. I went to the Nokia site and the fact they had a downloadable version of the software suite made me think that if I updated the installation that might sort it. It's a biggie, at 35MB, but if you have broadband it won't be a problem.
3. They also have a download to wipe the resgistry clean. That's only 44kb - but the fact they have it suggests that there might be a lot of issues that are difficult to resolve if you have installed the software once already.
4. The Nokia uninstaller is a pain. Actually, so is the installer. But persevere (with the unnecessary rebooting). Make sure you uninstall the apps, then run the registry cleaner.
5. Reboot and then install the downloaded Nokia apps.
6. When I tried to connect to the PC from the phone, I still got the message that the profile wasn't supported. At this point I tried a few swearwords I know, started to write to the Bluetooth device manufacturer (in Taiwan, so that could have got interesting), and then thought I'd try to connect from the PC to the phone - which hadn't worked earlier today.
IT DID!
I haven't a clue what was wrong, although the reinstall has sorted out a COM port setting problem that the initial install had created (mixing COM 0 and COM8).
I don't want to mess about with it now I've got it working, so I can't try and narrow it down for you.
Basically, all that rambling above summarises as 'uninstall the previous install - completely: use the registry cleaner to do it properly - then install the downloaded latest version, then try and connect from your PC to the phone'.
I'm sure there's a bit where you have to configure your Bluetooth software (it'll be different to mine, I guess), but it should detect the phone's capabilities automatically.
Oh yeah. The downloaded Nokia software doesn't have all that annoying 'honest, mate. I'm not spyware so you can install me, and if you say no I'm going to install anyway' garbage in it. Or the Nokia multimedia player (I bet that damned thing hijacked all my associations). Or if it did, I haven't seen it yet
Good luck.