I'm kind of with ragecgi on this, my set up is AE and Commotion accelerated with a Blue Ice board and I love the ease of workflow plus the fact Media 100 can export it's timeline to AE, which is nice.

I haven't used Shake yet but as it's node based set up is pretty much like Maya's I'd sure as heck like to get my grubbies on it.
In your shoes I'd go and see a few demos of AE, Combustion and Shake ask a lot of questions, see which is suited to the way you work then check your budget.
If your budget is tight then you don't need to go for the full AE production bundle the Standard version will do pretty nicely to start you off.