To be honest I'm not all that impressed by celebrity voice actors of any sort due to the fact that they have nothing to do with the gameplay itself.
As ironic as it might sound, the only ones that might influance me are not big celebrities. For example Vin Diesel (who isn't big right now) is known to be a gamer, and seems to have had a positive influance on the "Riddick" game(s). Asia Carrera surprised me when I checked her out in more detail and found out she was actually a pretty serious gamer, she's a porn star but I'd imagine if she was involved in a game project she might actually have some standards/input. Allegedly Tera Patrick was involved in Saint's Row 2 as a producer, not just as a promotional gimmick (her role being minor in a piece of DLC), she's another porn star but again she was involved in what turned out to be one of the best games of it's year of release (and probably THE best, I agree with Yahtzee about how great that game is).
If you just want to see John Cleese play nutty characters, and make jokes, you can find tons of movies and videos, some of which aren't that expensive. Paying $60 to see him voice a bit part in a video game doesn't strike me as being a wise investment even for a big time fan.
Also, to put things into perspective Meagan Fox (who I don't knock as much as many people) who has comparitively done very little compared to any of those people, would probably carry more weight with me than John Cleese. Not a lot mind you, but I at least know she plays video games given some comments where Shia Labouef claimed he wouldn't play with her on the set of Transformers 2. That's not much of a qualification, but to be honest I'm not even sure if John Cleese has so much as picked up a controller in like 15 years. The only video game project he was ever involved in to my knowlege was "Mony Python's Complete Waste Of Time" (not sure if there were any more games he/they did) and that is an ancient PC game.
Being a professional actor, with no real gaming experience I can think of (meaning he likely doesn't even have an opinion), I'd imagine anyone could pay him to do this. All it shows is that Peter Molyneaux is willing to pay for a well known personality... it says nothing about the game, the script, or even whether or not John Cleese is invested in the project since he might very well just dial it in like Ron Perlman has in a couple of games.