TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256 is a protocol (a subset of the TLS protocol family). Zombie POODLE and GOLDENDOODLE are vulnerabilities in some implementations of this protocol. So if the compliance firm is claiming, knowing only that your server accepts this cipher suite, that your server may be vulnerable to these attacks, they're correct. If the compliance firm is claiming that as soon as your server accepts this cipher suite, it's vulnerable to these attacks, then they're wrong.
These attacks are based on an analysis of error responses sent by a TLS server when it receives bad input (which may come from a malicious client or a man-in-the-middle. (This analysis includes the potential absence of a response as well as the timing of the response.) Both are padding oracle attacks. All TLS cipher suites that use CBC are vulnerable to padding oracle attacks if implemented naively. Pretty much every TLS implementation was vulnerable to Lucky Thirteen when it was disclosed in 2013, and some may still be vulnerable to variants of it, but OpenSSL and several other major TLS stacks now implement countermeasures which fully protect against padding oracle attacks if implemented correctly. Those countermeasures are intrinsically slow, and subtle, so you may not want to rely on them, but for the level of security expected for PCI compliance, they are sufficient.
If your server uses OpenSSL or the Windows TLS stack or most major TLS implementations, it's safe. (OpenSSL was vulnerable to another similar attack discovered at the same time though, dubbed “0-length OpenSSL” because it was very specific to OpenSSL's behavior.) What you mainly need to worry about is some middleboxes that decrypt TLS traffic (firewalls, load balancers, …). Even so, as long as you're applies all security patches, you should be fine (and if the latest firmware is still vulnerable, drop your vendor immediately).
In any case, you can use the scanner provided by the researchers who discovered the attacks to test your systems. This is the same scanner that Qualys (and undoubtedly others) use, so if Qualys says your system isn't vulnerable, you don't have a security problem: your only problem is to convince your auditor.
If your auditor is anywhere close to competent, they should either run this scanner or use a service that runs this scanner, and conclude that your system isn't vulnerable. But judging by their response, they may be less than competent. A good auditor would have known, and been able to explain, everything I've written here. It's also weird that the auditor only mentions those two attacks against CBC-based cipher suites and not older ones such as BEAST, Lucky Thirteen, etc.
How much do you care about supporting CBC cipher suites? While they can be implemented securely, that requires that all your servers and TLS-intercepting middleboxes are high quality, and it comes with a performance penalty. If you don't need them, I recommend disabling them. Generally, for TLS, a good balance between security and compatibility is to only use signature-based cipher suites (i.e. with ECDHE or possibly DHE in their name, in addition to RSA or ECDSA), with AEAD (CCM, GCM or CHACHA20_POLY1305). Some other cipher suites can be secure, but have increased risk of implementation vulnerabilities.
So my strategy with this auditor would be:
- Check if you actually want CBC cipher suites. If not, disable them and tell your auditor that this point is moot.
- If you do need CBC cipher suites, remind the auditor that these are implementation vulnerabilities and argue that Qualys says the implementation is vulnerable. If they're still not convinced, run the padding oracles scanner yourself and invite your auditor to do so as well.
- If the auditor really won't hear anything, you may be left with no choice but to change auditors. At this point we've strayed far away from cryptography and into the business realm.