People tend to forget the point of a tour. You're going out to promote your newest CD, and to get people interested in it, to buy it if they have not already. Any older song and classics a band plays are a treat for the fans. It's like Metallica going out and only playing Master of Puppets and Ride the Lightning songs. I would LOVE that, but I can see why they and the record label might be against the idea.
On the other hand, comparing a band like Maiden to us is just silly any way you slice it. Look at Paradise Lost for example. The first time they came here to play, the played NOTHING from Lost Paradise, and only one song from Gothic, and I was PISSED. I think when a band makes a first appearance, there's a bit of an obligation to play old material too, but for us, who play mostly festival shows, time iss limited, and we choose to promote the newest CD more then the old stuff. Someday when we film for the DVD, we'll play an hour or an hour and 30 minutes, and add in lots from our catalog.