Beautiful, thanks Dan! You were spot on about the page IDs not equalling 1-4.
Incidentally, I had a play with the code you suggested and it worked great, apart from only outputting the last 3 of the pages and outputting a blank id instead of the first page's id. However after subtracting 1 from mt_rand(1,count($pages)) before assigning the value $random_key it now works perfectly.
The final code, for anyone who's interested :
(not that it's very complicated, but I'm still a PHP newbie so I'm pretty stoked about it)
/* A function to pick a page at random from an array of the listed pages of the site */
$pages = get_pages(); //grab list of pages array - Cf. http://codex.wordpress.org/Function_Reference/get_pages
$randomKey = (mt_rand(1,count($pages)) - 1); //pick a page id at random from the list of page IDs
$page = $pages[$randomKey];
$pageLink = get_page_link($page->ID); //generate the page link for the selected page
return '<li><a href="'.$pageLink.'">Pick a page at random</a></li>';
Thanks again Dan! Much appreciated