I now have this recurring problem, also, after updating my 3gs to 4.2.1.
When I performed the update it failed and I lost everything on my phone - it was effectively a new phone to iTunes. So I did a restore and did the update again and all was ok, but after that, all the folders were gone and everything was in alphabetical order. As I have nearly 400 apps on my phone I have had to keep them organised before so this was completely unworkable.
So I spent a while sorting the main ones, but when I did a sync on iTunes everything went back to alphabetical order with no folders.
So, next, I tried moving a few in iTunes, this worked for the first sync, but the second sync reset everything again.
Not wanting to waste my time again, I tried arranging a few on the iPhone, and also created a few notes. Did a sync - all ok. Moved a few more, synced again ok. Thought I'd cracked it until I did an update of a couple of apps on the iPhone via wi-fi, at which point the screen froze for a couple of seconds and then guess what?! Alphabetical order, and no folders, again.
My phone is basically not usable at the moment as I have to search for every app. The initial failed update also wiped all of my contacts too (over 500!), but that's another story (why the **** aren't contacts part of a backup too?!)