I've always known him as Wally, it looks like "Waldo" is an american thing: http://en.wikipedia.org/wiki/Where's_Wally