OK here is how I fixed the problem.
1. Click Start, click Run, type regedit, and then click OK.
2. Locate and then click the following registry subkey:
3. In the right pane, look for DfsIrpStackSize, which probably won't exist
4. On the Edit menu, point to New, and then click DWORD Value.
5. Type DfsIrpStackSize, and then press ENTER.
6. In the Base box, click Decimal, type 10 in the Value data box, and then click OK.
If DfsIrpStackSize does already exist then just increase it's value to 10.
This comes from a Microsoft Knowledgebase article (http://support.microsoft.com/kb/906866) which refers to a problem with SP2 that is supposedly fixed with SP3. We already had SP3 installed so the hotfix referred to in the article won't install, however there was still no DfsIrpStackSize registry entry. Once we created that (on the machines that were having the problem) everything worked.
The machines that didn't have the problem also don't have a DfsIrpStackSize registry entry and seem to work fine without it, but on some machines it just seems to be necessary.