This happened to me because I was running 4.3.4 jailbroken. Just restore to 4.3.5 then to iOS5, that worked for me... assuming your situation is similar.
I've got the same problem iPhone4.. iTunes says my device (again iPhone4) is not Eligible.. I am running 4.3.3 Jailbroken How can I update to 4.3.5 prior to going to 5.0 ?