FIXED
Apparently 3.8 fixed the initial issue I was having where I had to use “cat.” Removing the categories would also cause the posts to disappear from the backend in 3.7.
I temporarily re-enabled category support for my post type and then removed the original categories from all of my posts.
They appear in wp_query results again and still exist in the backend and on the site.
Woo!
