I've got "Automatically install new apps" checked on all my iDevices, but it hardly ever does what it says. For example, I just downloaded three new apps to my computer and then did a Sync operation on two iPads and an iPhone -- none of the new apps showed up. On the App List, they each showed the button as Install. When I pressed the Install button on the App List for each of the affected apps, they then installed on the next Sync.
Just to keep me guessing, new apps WILL occasionally install correctly, but I've never figured out what magic circumstance triggered the proper behavior.