Nate already provided a very good answer but I would like to stress another point. Focusing on the passport is the wrong way to approach this. What happened is that you were refused a visa, apparently because you were suspected of having obtained another one fraudulently. It's not merely a ”passport error”.
You definitely need to get a new passport without a fake visa in it but at this point you can expect the US to have a record of your previous failed attempt at getting a visa. I have no idea how detailed it is or how long it will be kept on file but I would expect it to specify you were suspected of fraud and to remain live for at least 5 to 10 years (in Europe, it's more likely than not to expire after some time, in the US it might very well be kept indefinitely for all I know). A new passport is not enough to erase that.
Also understand that evidence of earlier fraud (or overstay, incidentally) speaks to your character and reliability and therefore does matter even if the stamp was not a US stamp. Conversely, having stayed previously in other countries (e.g. in Europe) while respecting the conditions of your visa for those countries is generally considered a plus. Stamps and visas from other countries are therefore definitely material to a visa application.
So, as Nate explained, you need to figure out exactly where you stand legally (whether there is a ban or not, etc.) and what you can do next (appeal, etc.) to confront the issue. And even if the chances of success appear low, you really need to confront it openly because any appearance that you are trying to hide it (e.g. if you get a passport to get rid of the earlier stamp and then fail to disclose that you were refused a visa) are likely to make matters even worse.