What is ZoneCheck and what does it have to do with my NS settings?

I'm talking about this paragraph here from the domain detail page:

WARNING: the .fr zone is only updated by AFNIC (the registry for that ccTLD), once a day from Monday to Friday. If your DNS settings pass AFNIC's zonecheck, your domain will be only be available to users throughout the world during the day of, 31/01/2009.

What happens if ZoneCheck isn't happy? The Nameservers I set can't be used? Or what?

An unhappy ZoneCheck means that the registry will not let you use those nameservers. Afnic proceeds with a test to see if your DNS are properly configured, and if they are not, then they will not apply the DNS to you domain name. When the ZoneCheck fails, it is accompanied by an error message that you need to pass on to your DNS provider (usually your web host) so that they can make the necessary changes. Once all is well, you can relaunch the DNS change request.

Right, and this particular hosting provider is saying:

"Ultimately our nameservers do not allow Zone Transfers on TCP Port 53 due to security reasons. AFNIC (the sole registrar of .fr domains) requires a nameserver query (via TCP port 53) prior to pointing the nameservers. This is an unfortunate situation which is unique to AFNIC. Other registrars are fully able to query our nameservers on TCP port 43 (the ICANN required port). Unfortunately there is not a work around on our end that would allow this query to go through. […]

We apologize for any inconvenience this causes, but because of the security risk we are not able to allow zone transfers on TCP Port 53 the way your registrar is trying to access them."

AFNIC says "These guys need to open their Firewall so we can query on this weird port", hostmonster says "get lost, use port 43 like everyone else". Poor customer who paid for his domain name and found a reliable hosting discover he can't migrate his .fr domain…

Is there anyway to raise this issue with AFNIC? There is no contact info I could find where a lowly customer like me can contact them.

AFNIC is registry, or rather, a trustee authority and not a registrar as indicated in the mail of your host - they are "above" registrars and responsible for the entire zone.

They are also not alone in requiring zonechecks. Many major ccTLDs (.IT, .DE, .NL …) also require and perform zonechecks.

Your webhost will need to comply with the dns standards required by the various registries that use zonechecks if they want their customers to be able to use their DNS.

Alternatively, you may use Gandi's DNS, and simply use our zone management interface to add the necessary entries to point to your web server etc. For personalized help on this, please see http://wiki.gandi.net/en/domains/management/gandi-dns-zonefile