Error when creating new contact: "Fatal error: Uncaught CRM_Core_Exception"
I wasn't able to recreate the error on the demo site: http://joomla.demo.civicrm.org/

But the problem you are running into sounds the same as this issue: https://issues.civicrm.org/jira/browse/CRM-16287

Perhaps there is some information there that will help?