Prior to SP1 for Server 2003, you could install cert services on a 2003 machine in a 2000 AD and it worked fine for issuing verion 1 certs.  Service Pack 1 included some security enhancements that broke this functionality, but you can still get it to work.
SP1 included code that audits certificate template changes.  When cert services start, it attempts to enumerate template objects and attributes in the AD before loading them in to memory.  It expects to find attributes from the 2003 schema.  Those attributes don't exist in the 2000 schema, so the templates fail to load.  With no templates loaded, the CA is unable to issue certificates, so all cert requests fail.
The simplest fix is to apply the 2003 schema changes to the 2000 AD.  Running forestprep is the easiest way to do this.