DNS, Do A Record wildcards have priority over more-specific CNAMEs?

The answer is generally "No" - the more specific record should win, so this should work as you described/expected. My guess is you have the wildcard A record cached somewhere, and need to wait for that cache to expire.

a quick test with BIND 9.6.2-P2/FreeBSD 8.1:
A zone containing the records:

example.net.                IN      A      127.0.0.2
*.test.example.net.         IN      A      127.0.0.1
specific.test.example.net.  IN      CNAME  example.net.

Resolves as follows:

% dig specific.test.example.net

; <<>> DiG 9.6.2-P2 <<>> specific.test.example.net
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 17222
;; flags: qr aa rd ra; QUERY: 1, ANSWER: 2, AUTHORITY: 2, ADDITIONAL: 2

;; QUESTION SECTION:
;specific.test.example.net. IN  A

;; ANSWER SECTION:
specific.test.example.net. 3600 IN  CNAME   example.net.
example.net.               3600 IN  A   127.0.0.2

;; AUTHORITY SECTION:
example.net.        3600    IN  NS  ns1.example.net.

;; ADDITIONAL SECTION:
ns1.example.net.    3600    IN  A   127.0.0.1

(Returns the CNAME)
and

% dig nonspecific.test.example.net

; <<>> DiG 9.6.2-P2 <<>> nonspecific.test.example.net
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 26980
;; flags: qr aa rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 2, ADDITIONAL: 2

;; QUESTION SECTION:
;nonspecific.test.example.net.  IN  A

;; ANSWER SECTION:
nonspecific.test.example.net. 3600 IN   A   127.0.0.1

;; AUTHORITY SECTION:
example.net.        3600    IN  NS  ns1.example.net.


;; ADDITIONAL SECTION:
ns1.example.net.    3600    IN  A   127.0.0.1

(Returns the wildcard A record)

According to your comment on the question:

when running dig -t ANY new-staging.example.com we get: new-staging.example.com. 82880 IN CNAME proxy.heroku.com.example.com. proxy.heroku.com.example.com. 86400 IN A 10.10.10.10

...you've misconfigured DNS. You need to set the target of the CNAME to proxy.heroku.com. - the final period is important! Without it, your DNS server is assuming you're referring to a host within your example.com zone - proxy.heroku.com.example.com - and that is being caught by the wildcard-record.