Quite a few people have pushed through the "it's incredibly hard" barrier and lived to tell that it's simpler than they'd feared, even for GUI tests. Look around a bit, and you'll find lots of good ideas for writing simple tests.
I find that the bits that are really difficult to test are the ones that have to "look right". For instance, I have some normal-mapping code with fairly well-defined requirements, but I'm interested in the final image on the screen. It's difficult to test that programatically: even if I take a screenshot and do a pixel-by-pixel comparison, what do I compare it to? An older result from the same program (hello, circular argument). Besides, the only real way to make sure that some of the stuff I do is correct is to move the viewpoint around and check that it looks "right". I could do a video capture and compare uncompressed, frames, but then I'd have to write and debug and test that code.
What I do instead isn't perfect, but it's pretty good: I write interactive test programs. When I do a build, I get about half a dozen simple little rotate-the-model popups; if they look "about right" I consider it a qualified pass. It's not pretty, but it's better than no tests at all.
On the other hand, I've been quite amazed at the number of tests I've been able to automate that I thought would be "test-by-hand" problems. (Actually, I have some ideas about testing that normal-mapping code.) One of the neat things about testing through an external library is that you have to understand that library very well to write good tests -- you have to understand what comes out the other side, and why.