Airmann,
At the briefing stage did you highlight your intention to do a CDA? As others have noted, some airspaces are suitable for it but others aren't - If your skipper felt your destination wasn't suitable for a CDA then that should have been sorted prior to TOD.
That said...
500fpm is entirely suitable for CDA purposes, as others have noted some airfields in the UK also allow rates less than that below TA (6000ft generally in the UK)...