Download latest redsn0w and use Extras > Fix Recovery -
Dev-Team Blog - redsn0w iOS5beta
The other tools you mentioned are VERY VERY VERY old and were never designed for iPad or 4.3.x
If this method does not work, best bet is to use iFaith to extract the 4.3.3 blobs from the device, then use the same tool to build yourself a custom pre-signed 4.3.3 firmware and install it. From there you can jailbreak using jailbreakme.com. Whilst you'll lose whatever's on it, at least you will get back a 4.3.3 JB iPad, which is still the golden firmware in terms of untethered goodness.