How can I create end-to-end tests for Mac (Cocoa) applications?
I think the key thing that I got from "Growing Object Orientated Software" was to decouple as much as possible from the UI. Without code to look at it's harder to give suggestions but with your revision I'd think that separating the "verify a label says.." bit from the UI. What is setting this message, and can you just test for that event?
The more you can decouple from the UI the more you can unit-test (quicker and easier) rather than integrating other frameworks or drivers of UI elements.
You might be interested in Square's KIF framework: http://corner.squareup.com/2011/07/ios-integration-testing.html
It looks really cool for integration/UI testing.
I believe you can use the Accessibility features to script the UI. I'd check the WWDC 2011 videos for one entitled "Design Patterns to Simplify Mac Accessibility". They did something similar in 2010.