Ultrasn0w doesn’t work on iOS 4.3.1 yet (even with iOS 4.3.1 + old baseband). The fix will be available soon. Here’s a warning from DevTeam for unlockers:
ultrasn0w users don’t update yet! We need to first release an update to ultrasn0w that fixes some incompatibilities when FW 4.3.1 is used on the older basebands supported by ultrasn0w. And remember once we do fix ultrasn0w for 4.3.1 (we’ll announce it here and on twitter), you must only get there via a custom IPSW from PwnageTool, Sn0wbreeze or xpwn! Don’t ever try to restore or update to a stock IPSW, or you’ll lose the unlock!