Updated June 2011: Aidan Gillen was in The Wire, which was another one of my favorite tv show. He's doing well as Littlefinger so I'm not too disappointed.
My fantasy cast for Littlefinger was Tom Hollander, who was Lord Cutler Beckett from Pirates of the Carribean.
Lord Petyr Baelish, also known as "Littlefinger," begins the series as Master of Coin (or treasurer) on King Robert's Small Council. He is also a master of court intrigue, with his brilliance matched only by his ambition. He is handsome and meticulously stylish, but also quite short, giving a double entendre to the mocking nickname Edmure Tully bestowed on him. Though a lord, his original holdings are possibly the smallest in all the Seven Kingdoms, situated on the smallest of the Fingers. His grandfather was Braavosi, and took the Titan of Braavos as his sigil. but wears a mockingbird as his crest instead.
During the War of the Ninepenny Kings, Petyr's father became friends with Lord Hoster Tully, and later used this friendship to have his son, Petyr, as a ward of Lord Hoster at Riverrun, the great castle of the riverlands. Petyr was raised alongside his social betters, the Tully children - Catelyn, Lysa and Edmure. He fell in love with Catelyn, who in turn loved him as a brother, but no more. When the betrothal between Catelyn and Brandon Stark was announced, Petyr challenged Brandon to a duel for her hand. Brandon won handily, but spared Baelish's life in compliance with Catelyn's pleas. Catelyn did not speak to him afterwards and burned the single letter Petyr sent after Brandon's death.
Lysa Tully, on the other hand, was in love with Petyr. She slipped into his bed one night while he was in a miserable, drunken stupor. The delirious Petyr may have mistaken Lysa for Catelyn, and indeed called her "Catelyn" that night. He has since claimed to have taken the maidenhood of both Tully sisters, however Catelyn's own private thoughts identify her husband Eddard Stark as taking her maidenhood and not Petyr. Later, Lysa became pregnant with Petyr's child. When Hoster Tully discovered this, he banished Petyr from his house and had Lysa drink Moon Tea to abort the pregnancy.
Baelish was given work at Gulltown by Lord Jon Arryn, to please Lord Arryn's young wife Lysa Tully. Petyr's wizardry with finances brought large sums of money into Gulltown and the Vale of Arryn, however, and Lord Arryn recognized Petyr's worth. He raised Petyr to the position of Master of Coin. His influence furnished him with many allies and contacts, including the City Guard of King's Landing. With these resources as a starting point, Baelish used a series of lies and double-crosses to achieve a meteoric rise to political power.
The only person that came to mind to play Petyr Baelish in this novel series A Song of Ice and Fire was the nasty Lord Cutler Beckett from Pirates of the Caribbean - Tom Hollander.