Also, I've found that horses bred for the "Big Lick" also are very pacy and require a bit more work to get them gaiting properly. Princess has it right, walk walk and walk some more than keep on walking. Ask for a slight increase in stride (a half go) and when you feel the horse starting to get rough, do a half halt and reorganize and ask again.
It sometimes takes a while, we just finished 90 days on a former performance horse who was nothing but pace without those stacks. After 90 days of walking and more walking and then "boot camp" he is now gaiting fairly consistently.
Just get out and enjoy and the more you walk the better those gaits get!