Did you happen to use fdisk in the procedure, to delete the old partition and make a new one before formatting? It's unnecessary, but some people do so.

And did you happen to answer NO to the question about large disk support it asks immediately after starting?

That's the most common reason for this situation.

If not, run fdisk /status from the MS-DOS prompt and report it's findings here.

Kees