I can do it again, but what happened was the screen went "funny" and looked a bit like an old computer screen when it starts up.
That was the
Recovery Mode screen. It should look something like this...

Then it displayed a highlighted option which I can't remember and being easily confused by technical things and a little indimitaded i decided to press the menu button as an "okay" to whatever it was asking me.

If you haven't used the
Volume Up/Down button to navigate to any other option before pressing on the
Home button, then you're just restarting the system only. (
look at the screen-shot, "reboot system now" will be highlighted as default)
What you need to do is, by using the
Volume Down button, navigate to "
wipe data/factory reset" then confirm "okay" by pressing the "
Home" button.
An easier method is to go to your [
Settings] > [
Privacy] and tapping on the [
Factory data reset] as posted
HereShoudl I try that again?
You can, but you'll lose all your saved data and contacts.
Back them up first.
Also, how can I get onto the "cellular data connection" and not wifi? Thanks!

What
Vostradamus meant is...you'll need to have a SIM with data (2G/3G) enabled inside your device.
And make sure your WiFi is temporary OFF, so that your carrier's data connection is in use.
Now, one thing I'm not sure if it will affect anything, but it was what I've gone through.
The first time you start your device after the Factory Reset, don't go for the Market first. Login with your Gmail account by logging into Gmail or Gtalk first.
When you're able to login there, then you go to the Market.
