Well a big thank you to thestealthyfox for pursuading me to go back and try this again. I also now have permalinks working (without the index.php!) using the above script from Niall Flynn.
It still wasn't easy though. I'm on a Mac so (in theory) my line endings are Unix by default, but I forced the line endings to Unix anyway.
After uploading as rewrite.script, I tried a permalink, and - 404 page not found. Tried re-saving the permalink settings, refresh, 404 page not found. Tried re-applying my theme, refresh, 404 page not found. Cleared the browser cache, refresh, 404 page not found.
Finally in desperation I tried a different permalink - and it worked! Hmm. So I went back to the previous permalink and added a short query string on the end along the lines of "?nocache=1" - and then it too sprang into life.
So I can only guess that Namesco might be using a caching layer that includes the caching of 404 errors. Then if you've already tried your permalinks out before adding the rewrite.script it carries on (for a while at least) serving up the old errors. My page edits are showing up fine though so who knows.
Anyway, thanks again!