I can't recall a similar complaint about Full Screen in the 4 months since Firefox 4.0 was released, and 5.0 is a security update for 4.0.

@ Xircal
What cor-el said.

Had this problem myself today but solved it quite differently:

1. Right click Firefox icon and choose Properties
2. Go to Compatibility tab
3. Click Use resolution 640x480 pixels
4. Ok and start Firefox
5. Firefox will now start (very lowres), but you should be able to change the size of the window.
6. Close Firefox and uncheck the 640x480 thingy
7. Start Firefox again and now all should be fine.