I can confirm that it's an issue with screen resolution. I have an AMD APU, with a 1366 x 768 screen, and I get the exact same issues. I suppose it just won't scale.
When I use an external monitor (a TV), the game plays just fine. Does anyone know enough about Touhou's internals to say where resolution scaling is handled?