Hello,
I have the same problem.
I have nokia E61 and it is recognized by the sms-client demo. But after I click "Finish" in the connect wizard, it says "Specified service not found". I have a HP notebook and it connects throug a HP Integrated Bluetooth module. When I go to the configuration of this bluetooth module in my Control Panel I see a local service "Bluetooth Serial Port" available..