Turns out the problem is that Vista thought my Contacts folder was a picture folder for some unknown reason.

Notice how the button is completely missing from the toolbar.

To change the folder so that Vista realizes it’s a contacts folder, right-click anywhere in the folder, and then choose Customize This Folder from the menu.

Now from the Customize tab, change the “Use this folder type as a template” to Contacts instead of Pictures, or whatever it was set to.

Now when you look at your Contacts folder, you’ll see the New Contact Group button as well as the other relevant buttons.

There should really be some better logic to determine the folder type.