Also Chiwetel Ejiofor. That entire storyline full of then-unknowns has done well.
Blooper: When David (Grant) is meeting Natalie for the first time, during the continuous shot of David going into Downing Street and then meeting the people from a distance he is wearing one tie. When they do the close-ups of David's conversation he has a different colored tie on. Word of God says Hugh Grant did that on purpose just to amuse himself.
Mythology Gag: The awkward scene at the wedding reception between Colin as a waiter and the attractive woman who turns out to be the caterer whose food he is criticising to make smalltalk with her was written for Four Weddings and a Funeral. It ended up being drafted out of the final film, but was used as one of the Charles audition scenes. It appears in its original form in the appendix at the back of the published screenplay. Curtis reveals in the commentary that he forgot to change one speaker identifier in the script, so the line is still attributed to "Charles."
"Who's Bill Nighy? Is he famous in England or something?" Yes, a little, but this was the film that elevated him to national treasure status.
Averted by Martine McCutcheon, a former-soap-star-turned-singer, who was given major billing and was about as well-received as the rest of the film. For some reason this didn't launch her onto any other roles.
What Could Have Been: Rowan Atkinson's character was originally going to appear in every single story (rather than just being a Cardinal Wolsey) with the strong implication that he was an angel. This is hinted in the airport scene where Atkinson's character gives Daniel a knowing glance after he "accidentally" allows Sam to get through airport security, and how he just sort of shows up at the counter in the jewelry store after the previous attendant walks off with a customer. Sort of the Christmassy equivalent to Sam from Trick 'r Treat.
Simon Pegg also auditioned for that part.
Sam was going to be a skilled gymnast, which would aid in his run through the airport. Ultimately Curtis couldn't figure out how to work it naturally into the story.