Interesting. In case this helps narrow it down, the "page" and "story" core types do not rely on CCK or any special modules (except if you have added more fields besides title and body) and they are created as user-defined types with a database INSERT during Drupal installation.
I disabled the outdated ecommerce module that the site isn't using anyway and I uninstalled two modules which were disabled and now the CCK types are working!
Still don't know what it was, but now it's fixed. :)
Thanks!