Winter is Coming has
made up a list of which characters will need to be cast in the series. It makes for interesting reading, as you realise how huge the cast could get.
The major roles that need to be cast would be, IMO:
Ser Barristan Selmy, Ser Loras Tyrell, Ser Gregor Clegane, Varys, Littlefinger, Grand Maester Pycelle, Renly Baratheon, Ser Ilyn Payne, Syrio Forel, Yoren, Lysa Tully, Ser Brynden Tully, Ser Edmure Tully, Lord Roose Bolton, Greatjon Umber, Lord Walder Frey, Bronn, Shae*, Gendry, Ser Beric Dondarrion, Shagga, Lord Tywin Lannister, Lord Commander Jeor Mormont, Samwell Tarly, Ser Alliser Thorne, Ser Janos Slynt, Maester Aemon, Hodor and Mirri Maz Duur.
* Although there has been speculation that Shae could be combined with the existing character of Ros from the pilot.
Characters who appear in the book but could be either reduced to minor roles or even eliminated entirely would be, IMO: Mya Stone, Lord Hoster Tully, Lord Wyman Manderly, Lady Maege Mormont, Thoros of Myr, Timmett, Kevan Lannister, Doreah and assorted Dothraki warriors, Northmen and Riverland lords and approximately four thousand Freys. Of those I'd probably be inclined to keep Maege Mormont and Wyman Manderly (both have potentially much larger roles later on, maybe in Book 5 or 6) but perhaps leave them unnamed until they are needed. Thoros of Myr also has an important role in the potential third and fourth seasons, but can be held back somewhat in Season 1 (maybe we only seem him and his burning sword in the distance or something).
It'll be interesting to see which actors are announced first and which ones they are aiming to include. I suspect announcements will be forthcoming in the next few weeks, with filming due to start in six weeks or so.
EDIT: Oh yeah, we need a new Daenerys as well