I bought a copy of "Super Mario Bros. 2" and mostly when I put it into the NES, it doesn't work. It shows a dark red screen with a huge black "something" in the middle. (I don't know how to describe it. It's a bunch of black pixels, but they all form one connected shape.) Once, I got it to work, but mostly it doesn't. The NES is almost new, rarely used, and it's the only game where it happens.
Also, in "Castlevania" the screen sometimes tends to get corrupted, replacing some objects in the game with letters and numbers. Even during gameplay: You load the game and it looks fine. And then when you walk through the first level, it happens.
Is there anything I can do to fix those things? Or should I consider buying the games anew?
Clean your games with Weimans and also clean your console connector in a sink with a toothbrush and it should all work fine when reassembled. Don't push the games down if you want your connector to last, too.
If your games are clean and you still have problems it is possible a chip inside the NES has gone bad. Unfortunately I can't think of the chip's part number.
Do the games run, do you hear music and only have graphical issues? If the games don't seem to run then maybe it's a dirty cartridge.
Is the big black "something" roughly the shape of the logo from the SMB2 title screen? If so, the palette is correct and games are starting to run, just using the wrong tiles. Game objects in CV being replaced with letters and numbers makes this sound even more likely.
From what I've read so far, I'd suspect one of the PPU address lines is making a poor connection. I'd do what 3gengames says: clean your cartridges and your NES edge connector. If you don't want to open your NES, you can use the official NES cleaning kit.
This might also be an issue with the connector. I've never really had any problems because all my NES's have come from ebay - they're frequently advertised as 'with new 72 pin' because these parts seem to age the fastest. They're very easy to replace and quite cheap to by alone. I remember when I first got mine I didn't know what was going on, and I ended up rigorously cleaning the pins of my SMB cartridge. I thought it would be a good idea to open it up, but didn't have the proper screwdriver... I ended up soldering around it to open it, and getting melted plastic everywhere! Stinky!