Something usually needs modified in the recorded web test. When I replay them it usually fails. Here's one of those times:
The error message says "1 dependant requests failed" The test results show an X next to the request that failed. Edit the recorded web test to find the request. Right click, select Properties, and change "Parse Dependent Requests" to False.