Several people have had trouble using the new XML data provider in SQL Server 2005 Reporting Services. Unfortunately, the feature came in very late in the cycle so the documentation is really sketchy. I have built a report that uses an Anagram web services at http://www.oorsprong.org/websamples.anagram/anagramservice.wso?WSDL. You can try out the methods at http://www.mindreef.net/tide/scopeit/start.do?referer=xmethods&url=http://www.oorsprong.org/websamples.anagram/anagramservice.wso?WSDL.
The report has two queries, one that calls the Languages method to get the list of Languages and one that calls Anagrams to get anagrams for a given language (sLanguageId) and length (iCharacters). Unforuntately, the data in the web service doesn't seem to return reliable data <g> but it should give you an example of using parameters.
Here's the report source.