OS 4.0 is not needed for Wireless Calendar Synch. I'm on 3.8 and it works fine. I have tested with 3.6 (6710) and 3.7 (7230) and it works fine, as well. Its just a software setting, as dpeters11 mentioned.
The one key to getting it to work immediately is to click on Synchronize Now after you make the PIM changes (on the Intellisync screen with Configure PIN button). After that, it should work fine.
For Address Book, Tasks, Memo Pad, etc to synchronize, it does require OS 4.0.
In the beginning the Universe was created. This has made a lot of people very angry and is widely regarded as a bad move.