$ rhc cartridges --config ~/.openshift/express-stg.conf jbossas-7 JBoss Application Server 7 web jbosseap-6.0 (*) JBoss Enterprise Application Platform 6.0 web jenkins-1.4 Jenkins Server 1.4 web nodejs-0.6 Node.js 0.6 web perl-5.10 Perl 5.10 web php-5.3 PHP 5.3 web python-2.6 Python 2.6 web python-2.7 Python 2.7 web python-3.3 Python 3.3 web ruby-1.8 Ruby 1.8 web ruby-1.9 Ruby 1.9 web jbossews-1.0 Tomcat 6 (JBoss EWS 1.0) web jbossews-2.0 Tomcat 7 (JBoss EWS 2.0) web zend-5.6 Zend Server 5.6 web diy-0.1 Do-It-Yourself 0.1 web 10gen-mms-agent-0.1 10gen Mongo Monitoring Service Agent addon cron-1.4 Cron 1.4 addon jenkins-client-1.4 Jenkins Client 1.4 addon mongodb-2.2 MongoDB NoSQL Database 2.2 addon mysql-5.1 MySQL Database 5.1 addon metrics-0.1 OpenShift Metrics 0.1 addon haproxy-1.4 OpenShift Web Balancer addon phpmyadmin-3.4 phpMyAdmin 3.4 addon postgresql-8.4 PostgreSQL Database 8.4 addon rockmongo-1.1 RockMongo 1.1 addon switchyard-0.6 SwitchYard 0.6 addon Note: Web cartridges can only be added to new applications. (*) denotes a cartridge with additional usage costs.
As Adam mentioned in https://bugzilla.redhat.com/show_bug.cgi?id=984837#c4, this is probably related to that issue. I'd even go so far as to say that this is probably a different manifestation of the same issue. We need to check that the version 0.3.0 of the postgresql cartridge is installed everywhere.
Closing, this was a caching issue. We cleared the cache multiple times and it eventually worked.