In this project the acceptance tests are written either before the story is started, or at the beginning of the iteration. We had a full testing team that was doing their best to figure out agile testing.
RE: GUI Testing
We were using Rational Robot and some custom built tools. We didn't use them for acceptance testing, but rather as a smoke test.
We are going through exactly the same problem in our project! We've been trying to implement what you proposed here as a solution to remedy the problem we faced. It's good to hear the solutions are working out for your team.
-BH
For GUI automation try the following:
WATIR
SW Explorer Automation
Selenium