It finally worked - I tracked down the problem to an issue with 64-bit windows where sometimes the iPad is not recognized in DFU mode. An error pops up saying that a connected device was not recognized in the middle of the jailbreak - perhaps that is the problem and interferes with the process.
What I did was to backup the iPad, then do a clean restore to factory settings (to minimize any problems from configurations coming from my previous settings - e.g. I had jailbroken 3.2.1 and I thought it might be trying to copy some settings from the previous set-up).
After that, I didn't sync the old files or set it up as a new ipad - I just left it in a pristine state.
I then tried the JB on my 32-bit Windows 7 HTPC, but first I installed iTunes on it, which installed all the iPad USB drivers, including the DFU mode driver. After that the Jailbreak went through without any problems!
So if anyone is having similar problems, check those USB drivers and maybe uninstall & re-install iTunes.