check out Batman for the NES too, by Hudson, for how NES games can look. It's down to skill and dealing with the restrictions in a smart manner. There's not many people around now that can do this like Ptoing, and there weren't very many then either.
Now that's a big part of the explanation, but also almost all nes developers had to deal with stricter restrictions then ptoing have used.
The NES can't by design set the palette per background tile as ptoing has done, it can only set it per 4 background tiles (that is per 16x16 square consisting of 4 8x8 tiles). It is possible to set the palette per tile by using special hardware in the game cartidge, but hardware for this didn't even exist until 1989, and even then it was way too expensive for most game makers to use. It was only used in a handful of games released outside Japan of which Castlevania 3 is the most well known.
This is why most NES game levels are made up of 16x16 blocks.
EDIT: When using the MMC5, as the hardware chip mentioned above is called, you can also use up to 16384 background tiles at once instead of the standard 256. so the only problem with that awesome title screen is the one 8x8 tile that has too many colors (on the upper part of the D), but that can easily be fixed by using a sprite overlay.
EDIT2: That title screen can most likely be displayed on a NES without any special hardware, if you switch tileset mid frame. and then use sprite overlays on the spots where the palette restrictions are violated.