Straight off, I have tried http://wordpress.org/support/topic/troubleshooting-wordpress-31-master-list?replies=7 and I am not "having a go at anyone".
I was waiting for the weekend to upgrade to version 3.1. The site has less traffic over the weekend and I have a bit more time for that type of activity.
Maybe it is my own fault, but I didn't realise the problems with 3.1 and permalinks until AFTER I upgraded.
I have spent the afternoon trying to get the custom permalinks working without success.
My suggestion is that the 3.1 upgrade should come with a health warning until the issue is resolved.
Niall