Ok, Heres some answers:
When I use "Run Now" for the report, from Reports, it doesn't complain, but neither do I see the report, or see it appear in the job history or Job Monitor
When I get the pop-up - thats it, just the number, theres no other text.
Theres nothing in any of the Event logs.
I took a look at 279679, but this states that it occurs after some time. The server was rebooted only 8 hours ago, but still fails.
This is using v10.1, rev 5629. I've not applied any hotfixes yet, as I've not seen anything in the hotfix docs that say they would be needed (I'm also unsure as to what order to apply them, or if they are cumulative).