Here’s an excellent example of the opposite happening: http://boards.straightdope.com/sdmb/showthread.php?t=62082. It’s at the bottom of the first post.
Burt Saxby? Tell him he’s fired.
I saw Dr. Strangelove several times before I realized that the bombardier was James Earl Jones. (I wonder if it’s disappointing to realize that your very first movie is the best one you will ever be in.)
I remember seeing Firefox (Clint Eastwood as a pilot who has to sneak into the Soviet Union to steal their newest airplane) when it first came out. A few years ago, I saw it again. I’ll be damned, his contact at the airbase is Sir Humphrey Appleby (also King George III and Dr. Cocteau).
And his other contacts in the Russian underground were both “that same guy” guys. The scientist that hides him in his trunk and smuggles him into the airbase was the bad guy from Raiders of the Lost Ark who picked up the burning hot headpiece from the Staff of Ra (“We are…heh heh…not thirrrsty.”)
And the younger Russian guy (“Take hees cigar…SMOKE EEET!!!”) that sees Firefox flying away then kills himself was Dim from A Clockwork Orange.
To further comments on The Matrix;
In Regards to Memento.
I was able to instantly tell Natalie and Trinity were both Carrie-Anne Moss.
I was completely and totally shocked that Cypher and Teddy were both “Joey Pants”.
I still find it amazing that the hubba-hubba studmuffin Jerry O’Connell, of Sliders and Crossing Jordan, is the same guy who, when younger, played the whiny, pudgy Vern Tessio in Stand by Me.
Capt. Stottlemeyer on Monk was the same guy as “Buffalo Bill” in The Silence of the Lambs.
Inspiring me to shout “Put the fucking lotion in the basket!” every time he comes on screen. 
Another one: Tim Matheson, Otter from Animal House, was the voice of Jonny Quest.
My roommate was just watching The Girl Next Door, and very excitedly pointed out to me that the sleazy pimp character was someone I should recognize… add a moustache, replace the sleaze with a rigid code of ethics, and presto, you get Bullock from Deadwood.
I was amazed (and very impressed) when I realised that the same actor, J.K. Simmons, played J. Jameson in the Spider-Man movies and Dr. Emil Skoda (rent-a-shrink) in Law & Order. That’s quite a range.
I couldn’t believe I just watched Batman Begins for the first time, from beginning to end, and never recognized Rutger Hauer as the obnoxious CEO. I mean, come on…Bladerunner is one of my favorite movies!
(I had also forgotten Gary Oldman was in BB…that guy is a chameleon!)
Clancy Brown played both The Kurgan in the original *Highlander * & Mr. Krabs in Spongebob Squarepants.
Um, no.
Sergeant Schultz was played by John Banner.
Wrong Sgt Schultz, you are thinking Hogan’s Heroes, CalMeacham was talking about Stalag 17 (1953) with Sig Ruman as Sgt. Schulz.
He also played Vern Schillenger in OZ and is the voice of the Yellow M&M. Range, indeed.
Speaking of Spiderman, Doc Ock in Spiderman 2 was the guy in Raiders of the Lost Ark that invaded the temple with Indy at the beginning. “Throw me the whip, I throw you the idol! No time to argue!”
And Career Sergeant Zim in the Verhoeven version of Starship Troopers. I mean, if that novel had ever been made into a movie.
I was watching an early episode of Inspector Morse not too long ago, and saw the credit for “Peter Woodthorpe as Max.” Peter Woodthorpe… where did I know that name from?
It turns out that the acerbic coroner who always gave Morse such a hard time is also the voice of Gollum in both the BBC radio version of Lord of the Rings and the animated Ralph Bashki version.
I caught OPEN RANGE the other day, and thought I recognized the corrupt marshal from somewhere. Credits (James Russo) didn’t spark my memory, so I IMDBed him. He played Mikey Tandino in BEVERLY HILLS COP, a movie I saw twenty years ago.
Holy shit!
Oh my Gawd!!
(sorry, I don’t know how to reply to two quotes in one post)