You on a 3G or a 3GS?
3G. IOS4 installs on 3G & 3GS, just not the first generation iPhone.
I ran another manual backup, and restored my device again. This time it let me install IOS4.
Problem is, now I have none of my metadata (most importantly my contacts) in my phone.
I'm restoring from backup, but now I am having the same exact problem trying to restore!!!