The story
Blend of celebrity + debutante + retard. Compare the suffix -tard. The first documented usage of the term was in a story about Paris Hilton published in the New York Post on 21 January 2006 ("Paris With a P"), which was followed by the second documented usage of the term in another story about Hilton published in the same paper five days later ("Unedited Paris Not Cute at All"). Sebastian Bach (of the band Skid Row) mentioned “Celebutard” as a potential band name in episode 1 of the reality show “Supergroup”, which aired on May 21st, of 2006.
Etymology from Wiktionary, CC BY-SA 4.0.