I have an iPhone 3GS running on iOS 4.0.0 with baseband 05.13.04. I would like to upgrade the phone to the latest unlock-able firmware out there. Unfortunately even though the phone has been Jailbroken/Unlocked for quite some time, Tiny Umbrella was not able to recover any save SHSHs so preserving the baseband during an upgrade might be a challenge... What is the best upgrade path in this case?

Here is the TU log, if it helps at all:

10/27/2011 11:13:09.242 For version [iPhone3GS 5.0b2 (9A5248d)] - This device isn't eligible for the requested build. 10/27/2011 11:13:09.258 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 5.0b2 (9A5248d) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:09.586 For version [iPhone3GS 4.3.5 (8L1)] - This device isn't eligible for the requested build.
10/27/2011 11:13:09.601 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 4.3.5 (8L1) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:10.086 For version [iPhone3GS 4.3.3 (8J2)] - This device isn't eligible for the requested build.
10/27/2011 11:13:10.117 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 4.3.3 (8J2) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:10.351 For version [iPhone3GS 4.3.1 (8G4)] - This device isn't eligible for the requested build.
10/27/2011 11:13:10.367 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 4.3.1 (8G4) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:10.914 For version [iPhone3GS 4.3b3 (8F5166b)] - This device isn't eligible for the requested build. 10/27/2011 11:13:10.929 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 4.3b3 (8F5166b) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:11.086 For version [iPhone3GS 4.3b2 (8F5153d)] - This device isn't eligible for the requested build. 10/27/2011 11:13:11.101 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 4.3b2 (8F5153d) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:11.586 For version [iPhone3GS 4.2b3 (8C5115c)] - This device isn't eligible for the requested build. 10/27/2011 11:13:11.617 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 4.2b3 (8C5115c) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:11.836 For version [iPhone3GS 4.0.2 (8A400)] - This device isn't eligible for the requested build. 10/27/2011 11:13:11.867 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 4.0.2 (8A400) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:12.539 For version [iPhone3GS 3.1.2 (7D11)] - This device isn't eligible for the requested build. 10/27/2011 11:13:12.554 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 3.1.2 (7D11) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:13.336 For version [iPhone3GS 4.0 (8A293)] - This device isn't eligible for the requested build. 10/27/2011 11:13:13.351 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 4.0 (8A293) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:14.133 For version [iPhone3GS 4.1 (8B117)] - This device isn't eligible for the requested build. 10/27/2011 11:13:14.148 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 4.1 (8B117) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:14.289 For version [iPhone3GS 4.2.1 (8C148a)] - This device isn't eligible for the requested build. 10/27/2011 11:13:14.304 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 4.2.1 (8C148a) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:14.836 For version [iPhone3GS 4.0.1 (8A306)] - This device isn't eligible for the requested build. 10/27/2011 11:13:14.867 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 4.0.1 (8A306) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:15.164 For version [iPhone3GS 3.1.3 (7E18)] - This device isn't eligible for the requested build. 10/27/2011 11:13:15.180 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 3.1.3 (7E18) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:15.617 For version [iPhone3GS 3.1 (7C144)] - This device isn't eligible for the requested build. 10/27/2011 11:13:15.648 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 3.1 (7C144) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:15.961 For version [iPhone3GS 3.0 (7A341)] - This device isn't eligible for the requested build. 10/27/2011 11:13:15.992 CYDIA DOES NOT HAVE YOUR SHSH FOR iPhone3GS 3.0 (7A341) THERE IS NO WAY FOR YOU TO GET THEM. SORRY. YOU ARE JUST TOO LATE.
10/27/2011 11:13:16.008 Finished saving SHSHs for [Adi’s iPhone]
10/27/2011 11:13:16.164 Caching shsh files...
10/27/2011 11:13:16.195 Found [0] shsh files to cache...
10/27/2011 11:13:16.211 Cached [0] shsh files