One of the biggest problems that's happened on projects that past few years was that web service changes that I was working on would break the UI that used it. This would cause testing to come to a halt until I could also add in the UI enhancements and redeployed it for test.
On the project that I'm working on now we're trying to implement some changes based on those problems.
First, we have set up a new web server to deploy a Development version of the web service to. This stems directly from the fact that new enhancements require changes to the web service and UI. The rules or additional features of the web service may break the UI until it is enhanced to take advantage of the new features. Having this new server now, I can break the web service and also use this development version to update the UI. When both are ready then they can be deployed for the tester.
Second, with multiple developers, sometimes one persons changes are ready to deploy for testing before the other persons. However, in an environment where everyone is using the main branch of the Source Code Repository (CVS for me) the code may not be in a deployable state due to one of the developers changes. In order to keep code synchronized with CVS, just in case my local hard drive dies, and have things in an easily deployable state, we are planning to branch each Story.
Timing is odd, it's something I was planning on doing, before I started implementing it I had the article The Story of the Branch Pattern sent to me. I'm doing basically the same thing.
Head is always deployable and the version that the Testers are testing. Defect fixes (unless they are very big) are done directly in Head so they can be redeployed quickly.
A new branch is created for each story. Development of the stories are done stand alone until they are ready to be tested, then they are merged in with Head and deployed for testing.
The only problem that I still have not figured out a way to work through is that this project has multiple developers. Each one is working on Web Service changes at the same time, and needs to have that web service deployed somewhere in order to make changes to the UI. We only have one development web server. Ultimately I think this could be fixed if I could figure out a way to get both the backend web server and the front end web server running on my local box. Each developer would then do everything locally until they are ready to merge. Until then I think the only solution is going to be to merge web service changes together outside of Head and deploy that merged version to the development web server.