[luap82]

I somehow accidentally changed the password on my iPhone and I tried to guess it but now I can't get into it at all, it's locked up. The phone says to plug it into iTunes and reset it from there, but when I plug it into iTunes it says I can't access it because it's locked. So I'm totally stuck. The Apple Store told me to plug it into iTunes, too. It's a total catch-22. What can I do? PLEASE HELP!!

[Cold Warrior]

Use iTunes to perform a restore. At the end choose set up as new device.

See this article, the section called Restoring your iPhone:
Backing Up, updating, and restoring your iPhone and iPod touch software

[luap82]

I can't perform a restore in iTunes because it says iTunes can't access the phone because it is locked.

[AKcrab]

iPhone and iPod touch: Unable to restore