After further experimentation, I have determined that once I get the dreaded 'Unable to initiate hotsync' message, I can get back to working state with following steps:

1. Remove laptop as a trusted device from Treo (Prefs->Bluetooth->Trusted Devices...)

2. Remove PC from Hotsync connection settings (Hotsync->Connection Preferences->Delete)

3. Add a new Hotsync connection (choose PC, Bluetooth, Find Devices). Choose 'Nearby Device' (do not choose KNOWN DEVICES) and choose my LAPTOP from nearby devices...

Hope this helps someone.