I might be over thinking this but...
The Boltons are currently the wardens of the north, but are they considered a great house? I guess now they are.
The Lannister's have a strong foothold as wardens of the West, and they are certainly a great house, but last I heard, Jaime was made Warden of the east since Jon Arryn's death. now THAT position is questionable.
Robert Arryn should be the warden of the east, and as a legitimate heir of Jon Arryn it should be indisputable, but we all know what "sweetrobin" is like.
The Tyrells are the wardens of the south, have been for many generations, and they seem strong and capable of keeping that title. However as they are the least established of the great houses. Martells, Lannisters, Starks, Arryns, and Greyjoys have all been kings in the past, ruling over their piece of the 7 kingdoms, but the Tyrells used to be banner men and stewards to their kings, the Gardeners.
If we are talking about Current Wardens, then the Boltons have by far the shakiest claim, but if we are talking only about the true great houses, then it is the Tyrells.