Alright I'm on 5.0.1 now and this was probably the most painless update and jailbreak with RedSn0w I ever had o.o Thanks again iLLmAtlc!
One question though, I noticed that my iPhone wanted to download 6.1.3 OTA and was already halfway through so I rushed to Cydia and got the "No Update" tweak which seems to work though can I check somewhere over SSH if I have a partial update file downloaded that eats space?
Okay I have a slight problem now. I was doing a essential Cydia Upgrade when I got a popup saying "6.1.3 is now available. View / Cancel" I clicked Cancel of course though now I can't access the setting app anymore, whenever I do I get to the Update screen saying "No Update Tweak installed" "Working like a charm!" and it won't let me back out from there :/
And another edit, I downloaded SBSettings and a respring fixed it though is there a way I can make sure a OTA update never gets through?
EDIT3: Okay everything is going smoothly so far and I installed my Cydia apps again though now that I started iTunes and set up up as a new iPhone it shows that 2.6gb is used by "Other" o.o Now I'm aware Other usually includes Jailbreak things but I haven't even messed with Winterboard yet and before the update I had 900mb used as other which seems reasonable but now I wonder what is 1.7gb big on a freshly installed iPhone? :/ Is there anyway to see what exactly makes up "Other"? I currently run a search with iFunBox for every file that exceeds 50mb and see if I find anything suspicious.