Good news from the iPhone Download Blog; an update for UltraSn0w is nearing its final stages of testing and will shortly be released.
MuscleNerd, one of the key Dev members, confirmed by way of Twitter that UltraSn0w will shortly unlock iOS 4.3.1 for existing unlockers. The update will not unlock any new basebands.
If you have not previously Jailbreaked your iDevice you will need to wait a bit longer for a full carrier unlock.