How do workflow and service oriented architecture relate?
The real question is how service oriented architecture (SOA) and business processes relate.
Service orientation is about how to organize and utilize distributed capabilities that could be under the control of different owners.1 Business Process Management (BPM) is about modeling, designing, deploying and managing business processes.2 Business processes are the capabilities, or the users of those capabilities. Workflow is a technology that builds the automated part of a business process. It integrates human decision with synchronous and asynchronous software systems. Of course this is somewhat recursive because a workflow could use other services in its implementation.
For me, SOA and BPM are not in conflict. People talk about layering BPM on top of SOA. Or that SOA is for IT folks, and BPM is for business people. In today's world, business cannot afford to have people who just think IT, or just think business. Given the way the human mind works, multiple models are often needed to think about certain problems.3 SOA and BPM are two different ways to think about the same problem: how organizations can best accomplish their missions. Thinking about business process will transform how you architect your services. Architecting your services will impact how you model your business processes.
1 For more information about service oriented architecture take a look at the Reference Model that the OASIS TC that I am a member of has produced: http://www.oasis-open.org/committees/download.php/18486/pr-2changes.pdf
2 See http://ww6.infoworld.com/products/print_friendly.jsp?link=/article/06/02/20/75095_08FEbpmmap_1.html
3 See "Mental Models" by P.N. Johnson-Laird in Foundations of Cognitive Science edited by Michael I. Posner