So, the previous checklist did not quite work out as smooth as it was supposed to. It was correct in theory, but not in practice.
First of all, after backing up, restoring to a clean 4.3.1 my 4.2.1 backup did not want to restore. iTunes gave me a “iTunes could not restore the iphone because the password was incorrect” error which is really weird since I do not encrypt my backups. Anyway, thanks to Jamie, I was able to solve this problem.
What I did was that I restored my iPhone as a new phone, let it backup, then I grabbed the key in Manifest.plist and put it into my old backup. Then I restored the 4.3.1 firmware again, and this time I was able to restore the previous 4.2.1 backup.
Next problem was Pkgbackup. It turns out that using Pkgbackup going from 4.2.1 to 4.3.1 with Cydia 1.1.1 gets your apt sources messed up. Thanks to the Internet Hive mind, I was able to find this post detailing how to reset Cydia.
Anyway, everything is fine now. Now, to take care of the iPad…