What is the file name of the ipsw, sounds like you have one of the betas and I'm guessing you don't have a dev account?
I am pretty certain its the right one,filename is iPad2,1_5.0_9A334_Restore.ipsw. Even if it was the wrong file why would it stop me doing a factory settings restore?
Take a look at this: http://leimobile.com/this-device-isnt-eligible-for-the-requested-build/
While your device has never been jailbroken it could still be the case that your host file (for whatever reason) blocks connection to the Apple servers needed for the activation.
Yeah could be right and I am going to give that a go sometime today but why would that stop me restoring 4.3.5, Is it something to do with the iTunes Beta?