Are you using Adaptec 4.0? Back when it was the latest version of EZCD, CDDB.org was totally free. However, now they've sold out, taking all of the user submissions that made them what they are, and charge for the service now (I forget what they're called now). But now the best free CDDB is freecddb.org. All current software uses the freecddb server, such as EAC, but I'm not sure of Adaptec EZCD 4.0.
edit- going to cddb.org presents their current website, Gracenote. And now I'm not so sure their services are fee-based. Maybe they just changed their format, thereby breaking software that used it.