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)
dig -t ANY new-staging.example.com? – nickgrim Mar 29 '11 at 15:24