After banging my head against a wall almost all day, I've narrowed this down a bit.
If I deactivate and then re-activate WooCommerce, hitting /shop/ on my site takes me to the shop base page. Clicking on any of the categories however, takes me to just the media link for the thumbnail image I used.
Once I go in and change my permalink settings to use "shop" in the product category base, and /shop/%product_cat% as my Custom Base, i am able to navigate to /shop/somecategory just fine, including products, etc... HOWEVER, navigtating back to /shop/ once I've clicked save on the Settings -> Permalink page literally just displays my standard homepage URL content.
I tried doing a live preview using the TwentyTwelve theme, and everything seems to display properly, so clearly there's something about my theme that's doing this, but I'm not sure where to start digging.
I'm quite comfortable editing PHP, does anyone have a suggestion of where I might start?