This seemed very odd at first, as I had never noticed a delay before with these web parts, so my first thought was a migration issue. But why would a migration only cause the web part to work slower.
So with the help of my good friend Google, I was able to find a blog post  that offered the following:CQWP ignores the following items:
- Items are check-out
- Items are not published and not-approved
Following the advice in the same blog post, I wrote a console app that targeted all the CQWP and changed the "UseCache" property to false.
Just like magic the items I created are now showing up immediately in their respective CQWPs.
Keep in mind this may not be the best solution for a site with a high load or CQWPs that are running large queries. You'll need to weigh the benefits of performance against immediate results. In most cases users will understand if there is a small delay as long as they have an understanding of the situation.