Die Beschwerde ist zulässig (1.), aber unbegründet (2.).
1. Die Beschwerde ist zwar entgegen § 133 Abs. 3 Sätze 1 und 2 VwGO nicht innerhalb der Frist von zwei Monaten nach Zustellung des Urteils des Verwaltungsgerichts begründet worden. Auf seinen Antrag ist dem Kläger aber Wiedereinsetzung in den vorigen Stand zu gewähren.
Nach § 60 Abs. 1 VwGO ist dem Kläger Wiedereinsetzung in den vorigen Stand zu gewähren, wenn er ohne sein Verschulden gehindert war, die versäumte Frist einzuhalten. Ein Verschulden ihres Prozessbevollmächtigten muss sich eine Prozesspartei wie eigenes Verschulden zurechnen lassen (§ 173 VwGO i.V.m. § 85 Abs. 2 ZPO). Die Vorschrift des § 85 Abs. 2 ZPO bezieht sich indessen nicht auf ein Verschulden etwaiger Hilfspersonen, deren sich der Beteiligte oder sein Bevollmächtigter bei der Wahrnehmung seiner verfahrensrechtlichen Aufgaben bedient (Urteil vom 8. Mai 1991 - BVerwG 3 C 68.89 - Buchholz 310 § 60 VwGO Nr. 172 S. 39, 40). Dies ist hier der Fall, denn die Fristversäumung beruht nach dem glaubhaften Vortrag des Klägerbevollmächtigten ausschließlich auf dem fehlerhaften Verhalten einer Hilfskraft.
Der Prozessbevollmächtigte des Klägers bringt unter anwaltlicher Versicherung der Richtigkeit seines Vorbringens sowie unter Vorlage einer eidesstattlichen Versicherung seiner Angestellten Frau B. vor, bei Eingang des Urteils seien die Fristen zur Einlegung der Nichtzulassungsbeschwerde auf den 30. Mai 2003 und die Frist zur Begründung auf den 30. Juni 2003 notiert und im Kalender eingetragen worden. Am 14. Mai 2003 habe er die Beschwerde gegen die Nichtzulassung gefertigt und seiner Angestellten Frau B. Anweisung erteilt, die Frist für die Einlegung der Beschwerde gegen die Nichtzulassung der Revision im Fristenkalender zu streichen. Diese habe jedoch nicht nur die Frist für die Nichtzulassungsbeschwerde, sondern entgegen der Anweisung auch die Frist für die Begründung der Beschwerde gegen die Nichtzulassung der Revision im Fristenkalender mit dem Vermerk "erl." und ihrem Diktatzeichen versehen. Auch habe sie die Vorfrist für den 23. Juni 2003 gestrichen. Daher sei ihm die Akte nicht rechtzeitig vor Fristablauf vorgelegt worden. Am 1. Juli 2003 habe er sich an die Akte erinnert und den Fehler festgestellt. Frau B. sei eine ausgebildete Rechtsanwalts- und Notarsgehilfin. Seit dem 1. Oktober 2000 sei sie bei ihm beschäftigt und verfüge über eine achtzehnjährige Berufserfahrung. Sie bearbeite u.a. den Posteingang und sei für die Fristennotierung zuständig. Auch für die Überwachung des Fristenkalenders, die Vorlage der Akten, die Vorfristen und die Fristabläufe sei Frau B. zuständig. Es unterliege weiterhin ihrem Aufgabengebiet, die Erledigung der Fristabläufe zu überprüfen, bevor sie in den Feierabend gehe. Bislang habe Frau B. diesen Aufgabenbereich stets zu seiner vollsten Zufriedenheit ausgeführt, und es sei noch zu keiner Fristversäumung gekommen. In seinem Büro herrsche die generelle Anweisung, dass Fristen nur zu streichen seien, wenn das entsprechende Schriftstück in den Postaugang gegeben werde. Diese Anweisung sei aufgrund des Versäumnisses der Angestellten ins Leere gegangen.
Nach dieser glaubhaften Einlassung ist das Versäumnis somit darauf zurückzuführen, dass die erfahrene und ansonsten zuverlässig arbeitende Büroangestellte Frau B. entgegen der ihr erteilten Weisung nicht nur die Frist für die Einlegung der Nichtzulassungsbeschwerde, sondern darüber hinaus auch die Begründungsfrist und die zugehörige Vorfrist im Fristenkalender als erledigt kennzeichnete. Damit verstieß sie zugleich auch gegen die im Büro des Prozessbevollmächtigten des Klägers bestehende allgemeine Weisung, Fristen im Fristenkalender nur dann als erledigt zu kennzeichnen, wenn das entsprechende Schriftstück in den Postausgang gegeben ist. Dieses Fehlverhalten der Angestellten kann dem Prozessbevollmächtigten des Klägers nicht als selbstverschuldet angelastet werden, weil er mit einer solchen bislang nicht vorgefallenen Eigenmächtigkeit der Angestellten nicht zu rechnen brauchte (vgl. BGH, NJW 2001, 1578). Vielmehr durfte er darauf vertrauen, dass die Angestellte seine Weisung richtig ausführen würde und dass ihm die Akte aufgrund der weiteren Eintragungen im Fristenkalender rechtzeitig zur Anfertigung der Beschwerdebegründung vorgelegt werden würde. Eine Pflicht des Prozessbevollmächtigten, sich über die richtige Ausführung seiner Weisung zu vergewissern, bestand nicht.
2. Die Beschwerde ist aber unbegründet.
a) Ein von der Beschwerde behaupteter Verfahrensmangel des Urteils (§ 132 Abs. 2 Nr. 3 VwGO) liegt nicht vor. Das Verwaltungsgericht hat weder den Überzeugungsgrundsatz aus § 108 Abs. 1 Satz 1 VwGO (aa), noch den Begründungszwang aus § 108 Abs. 1 Satz 2 VwGO (bb) verletzt.
aa) Das Verwaltungsgericht hat sich mit dem angefochtenen Urteil in den Grenzen der Befugnis gehalten, "nach seiner freien, aus dem Gesamtergebnis des Verfahrens gewonnenen Überzeugung" entscheiden zu dürfen (§ 108 Abs. 1 Satz 1 VwGO).
Die "Freiheit", die dieser sog. Überzeugungsgrundsatz dem Tatsachengericht zugesteht, bezieht sich auf die Bewertung von Tatsachen und Beweisergebnissen, d.h. auf die Bewertung der für die Feststellung des Sachverhalts maßgebenden Umstände (Urteil vom 17. Januar 1980 - BVerwG 5 C 7.79 - Buchholz 431.1 Architekten Nr. 5 S. 16 <17>). Sie ist nach der einen Seite hin begrenzt durch das jeweils anzuwendende Recht und dessen Auslegung. Alles, was (noch) Rechtsfindung ist, entzieht sich - eben deshalb - einer Deckung durch den Überzeugungsgrundsatz (vgl. dazu die Hinweise etwa in den Beschlüssen vom 11. Februar 1976 - BVerwG VI C 3.76 - Buchholz 310 § 108 VwGO Nr. 84 S. 8 <9> und vom 6. Februar 1978 - BVerwG VI C 17.77 - Buchholz 310 § 139 VwGO Nr. 46 S. 3 <6>). Nach der anderen Seite hin ergibt sich die Grenze daraus, dass der Überzeugungsgrundsatz nicht für eine Würdigung in Anspruch genommen werden kann, die im Vorgang der Überzeugungsbildung an einem Fehler leidet, z.B. an der Missachtung gesetzlicher Beweisregeln oder an der Berücksichtigung von Tatsachen, die sich weder auf ein Beweisergebnis noch sonst wie auf den Akteninhalt stützen lassen (Urteil vom 25. Mai 1984 - BVerwG 8 C 108.82 - Buchholz 448.0 § 11 WpflG Nr. 35). Diesen Grundsätzen hat das Verwaltungsgericht nicht zuwidergehandelt.
(1) Die Beschwerde bringt vor, das Gericht habe sich nicht damit auseinander gesetzt, dass der Kläger noch vor Zugang des ablehnenden Bescheides des Bundesamtes für den Zivildienst das polizeiliche Führungszeugnis eingereicht habe. Wäre der Bescheid des Bundesamtes ein paar Tage später erstellt worden, wäre der Kläger mit Sicherheit anerkannt worden.
Der Einwand geht fehl, denn das Verwaltungsgericht hat sich mit den zeitlichen Umständen der Einreichung des Führungszeugnisses sowie der in diesem Zusammenhang eingetretenen Fristversäumung auseinander gesetzt (Urteil S. 7 ff.). Dabei hat es sowohl Mängel im organisatorischen Bereich als auch Störungen in der psychischen Verfassung des Klägers in Betracht gezogen. Da es insgesamt keine Gründe gesehen hat, die die verspätete Übersendung des Führungszeugnisses rechtfertigten, hat es die Voraussetzungen für eine Anerkennung nach Aktenlage verneint. Das Verwaltungsgericht hat also lediglich den von ihm zutreffend erfassten Sachverhalt anders gewürdigt, als es der Kläger für richtig hält.
(2) Außerdem wird vom Kläger vorgebracht, das Verwaltungsgericht habe ausweislich der Urteilsgründe seine Bereitschaft zur Inkaufnahme der lästigen Alternative eines verlängerten Dienstes nicht als tragendes Indiz gewürdigt, sondern nur als eines unter vielen. Dies ergebe sich schon daraus, dass es diese Frage erst im Zusammenhang mit der "Vollprüfung" aufgeworfen habe, obwohl es sich mit ihr bereits im Rahmen des "ersten Prüfungsschrittes" hätte auseinander setzen müssen. Zu Unrecht habe das Verwaltungsgericht auch zu seinem Nachteil gewürdigt, dass er sich noch nicht um eine Zivildienststelle gekümmert habe. Das Gericht lasse dabei außer Acht, dass keine Zivildienststelle eine Zusage gebe, solange kein Anerkennungsbescheid vorliege.
Die Rüge greift ebenfalls nicht durch. Zum einen liegt der Schwerpunkt des Vorbringens in einer behaupteten fehlerhaften Anwendung des Rechts der Kriegsdienstverweigerung und nicht in einem angeblichen Verstoß gegen den Überzeugungsgrundsatz. Die Frage, wie sich die Entscheidung des Gerichts für eine "Vollprüfung" zur Bedeutung des verlängerten Zivildienstes als "lästige Alternative" verhält, betrifft nämlich die richtige Anwendung des materiellen Rechts und würde erst im Falle einer zugelassenen Revision Bedeutung gewinnen können. Zum anderen gibt die Beschwerde das Urteil hinsichtlich der Anstrengungen des Klägers um eine Zivildienststelle nicht richtig wieder. Es hat zu seinen Ungunsten nicht bewertet, dass er eine Zivildienststelle noch nicht "fest" habe, sondern dass er "sich bislang weder um eine Zivildienststelle bemüht hat noch sich sonst in sozialer Weise engagiert hat" (Urteil S. 9). Daher kam es auf die Frage nicht an, ob er ohne Anerkennungsbescheid überhaupt eine Zusage von einer Zivildienststelle erhalten konnte.
bb) Das Urteil verstößt auch nicht gegen den Begründungszwang aus § 108 Abs. 1 Satz 2 VwGO; danach sind in dem Urteil die Gründe anzugeben, die für die richterliche Überzeugung leitend gewesen sind. Speziell für Verfahren, in denen der Wehrpflichtige seine Anerkennung als Kriegsdienstverweigerer aus Gewissensgründen begehrt, hat das Bundesverwaltungsgericht aus dieser Vorschrift gefolgert, dass die Urteilsbegründung des Verwaltungsgerichts eine Würdigung des Beweisergebnisses im Einzelfall und eine auf die Person des betroffenen Wehrpflichtigen und die sonstigen maßgebenden konkreten Umstände abgestellte Angabe derjenigen Gründe enthalten muss, die für die Entscheidung über sein Anerkennungsbegehren maßgebend gewesen sind; danach sind insbesondere formelhafte Darstellungen der zur Anwendung des Art. 4 Abs. 3 GG entwickelten Maßstäbe und Bezugnahmen auf den "Gesamteindruck" des Gerichts vom Wehrpflichtigen nicht ausreichend (vgl. z.B. Urteil vom 18. Februar 1981 - BVerwG 6 C 159.80 - Buchholz 448.0 § 25 WpflG Nr. 119; Urteil vom 16. Januar 1985 - BVerwG 6 C 54.82 - Buchholz 310 § 108 VwGO Nr. 158).
Die Beschwerde bringt vor, das Verwaltungsgericht habe im Urteil ausdrücklich erklärt, dass es sich auf einen Gesamteindruck gestützt habe, der "nicht mit Worten in der Sitzungsniederschrift festgehalten oder in den Entscheidungsgründen wiedergegeben werden kann ...". Es habe also tatsächlich die Gründe, auf die es seine Entscheidung stütze, im Urteil nicht, zumindest nicht vollständig angegeben. Es müsse möglich sein, auch "Elemente der nicht-verbalen Kommunikation", die für die Entscheidung maßgeblich gewesen seien, in Worten auszudrücken, ließen sich doch sonst die Gründe für die Entscheidung nicht überprüfen, so dass jeder Willkür Tür und Tor geöffnet wäre.
Der Beschwerde ist darin Recht zu geben, dass die Formulierung auf Seite 8 des Urteils, wonach "der in der Verhandlung gewonnene Gesamteindruck, der letztlich nicht mit Worten ... in den Entscheidungsgründen wiedergegeben werden kann, weil in ihn Elemente der nicht-verbalen Kommunikation grundlegend mit einfließen" zu Missverständnissen Anlass gibt. Was nicht in Worten ausgedrückt werden kann, darf auch nicht bestimmend in ein Urteil Eingang finden. Jedoch enthält das Urteil nicht den Fehler, der aufgrund der von der Beschwerde beanstandeten Formulierung zu erwarten wäre. Die Urteilsgründe führen nämlich nachfolgend eine ganze Reihe von Erwägungen an, aus denen sich der "Gesamteindruck" nach Ansicht des Gerichts zusammensetzt, und fassen diesen Eindruck nachvollziehbar in Worte. Daher wohnt dem Urteil auch unter Beachtung der missverständlichen Formulierung nicht der Fehler inne, dass es auf nicht in Worte gefassten Begründungserwägungen beruht.
b) Ebenso bleibt die Abweichungsrüge (§ 132 Abs. 2 Nr. 2 VwGO) ohne Erfolg. Eine die Revision gemäß § 132 Abs. 2 Nr. 2 VwGO eröffnende Abweichung von der Rechtsprechung des Bundesverwaltungsgerichts ist nur dann hinreichend bezeichnet, wenn die Beschwerde einen inhaltlich bestimmten, die angefochtene Entscheidung tragenden abstrakten Rechtssatz benennt, mit dem die Vorinstanz einem in der Rechtsprechung des Bundesverwaltungsgerichts aufgestellten ebensolchen die Entscheidung des Bundesverwaltungsgerichts tragenden Rechtssatz in Anwendung derselben Rechtsvorschrift widersprochen hat (vgl. Beschluss vom 21. Juni 1995 - BVerwG 8 B 61.95 - Buchholz 310 § 133 <n.F.> VwGO Nr. 18). Das Aufzeigen einer fehlerhaften oder unterbliebenen Anwendung von Rechtssätzen, die das Bundesverwaltungsgericht in seiner Rechtsprechung aufgestellt hat, genügt hingegen weder den Zulässigkeitsanforderungen einer Divergenz- noch denen einer Grundsatzrüge (vgl. Beschluss vom 17. Januar 1995 - BVerwG 6 B 39.94 - Buchholz 421.0 Prüfungswesen Nr. 342 S. 55). Darauf beschränkt sich aber das Beschwerdevorbringen.
Der Kläger rügt die Abweichung des verwaltungsgerichtlichen Urteils vom Urteil des Bundesverwaltungsgerichts vom 19. August 1992 - BVerwG 6 C 25.90 (Buchholz 448.6 § 5 KDVG Nr. 5). Dort werde ausgeführt, die "eingehendere Prüfung" habe sich zunächst - in einem ersten Prüfungsschritt - auf diejenigen Umstände beschränken müssen, die nach seiner Auffassung zu Zweifeln an der Glaubhaftigkeit der geltend gemachten Gewissensentscheidung Anlass gegeben hätten. Das Verwaltungsgericht habe aber ausweislich der Niederschrift über die mündliche Verhandlung einen Beschluss erlassen, wonach Beweis zu erheben sei über die Gründe, die den Kläger bewogen hätten, den Kriegsdienst mit der Waffe zu verweigern. Es habe nicht vorab einen Beschluss erlassen, Beweis zu erheben über die Gründe, die zur verspäteten Einreichung des polizeilichen Führungszeugnisses geführt hätten. Dazu sei der Kläger nur informatorisch gehört worden. Das Verwaltungsgericht habe sowohl bei der von ihm gewählten Abfolge der Prüfungsschritte als auch bei der rechtlichen Würdigung im Rahmen des jeweiligen Prüfungsschrittes der wesentlichen Neuordnung durch das KDVNG nicht hinreichend Rechnung getragen.
Die Abweichungsrüge genügt den Anforderungen bereits deshalb nicht, weil kein abstrakter Rechtssatz im streitgegenständlichen Urteil benannt wird, mit welchem das Verwaltungsgericht von einem ebensolchen Rechtssatz im angeführten Urteil des Bundesverwaltungsgerichts abgewichen sein soll. Das Vorbringen ist vielmehr in der Art einer Revisionsbegründung formuliert. Zur Berücksichtigung von Revisionsgründen bedarf es aber erst der Zulassung der Revision.
Darüber hinaus liegt auch der behauptete Rechtsanwendungsfehler im Urteil des Verwaltungsgerichts nicht vor. Das Bundesamt für den Zivildienst hatte den Antrag auf Anerkennung des Klägers als Kriegsdienstverweigerer mit Bescheid vom 21. November 2001 zurückgewiesen, weil er entgegen der Anforderung in § 2 Abs. 2 Satz 3 KDVG in der damals geltenden Fassung des Art. 2 Nr. 1 des Zweiten Gesetzes zur Änderung des Kriegsdienstverweigerungs-Neuordnungsgesetzes vom 30. Juni 1989 (BGBl I S. 1290) kein Führungszeugnis nach § 28 Bundeszentralregistergesetz vorgelegt hatte und der Antrag somit nicht im Sinne von § 5 Nr. 1 KDVG vollständig war. Das Verwaltungsgericht hat sich entsprechend der vom Kläger zutreffend zitierten Rechtsprechung des Bundesverwaltungsgerichts verhalten, indem es in der mündlichen Verhandlung daraufhin in der Art einer "eingehenderen Prüfung" in entsprechender Anwendung der §§ 9 ff. KDVG die Gründe erörtert hat, welche den Kläger an der rechtzeitigen Vorlage des Führungszeugnisses gehindert und Zweifel an der Ernsthaftigkeit seines Antrages begründet hatten. Für diese Erörterung bedurfte keines vorherigen Beweisbeschlusses. Nach dieser Erörterung hat das Verwaltungsgericht sich ausweislich der Niederschrift über die mündliche Verhandlung zur Beratung zurückgezogen und durch Verkündung eines Beschlusses über die Parteivernehmung des Klägers zu seinen Beweggründen zur Kriegsdienstverweigerung zum Ausdruck gebracht, dass es die Zweifel an der Ernsthaftigkeit durch die Zwischenerörterung nicht als ausgeräumt ansah. Damit hat das Verwaltungsgericht die in der Rechtsprechung des Bundesverwaltungsgerichts entwickelten Verfahrensschritte zur Prüfung in Rechtsstreitigkeiten um die Anerkennung von Kriegsdienstverweigerern eingehalten.
3. Der im Übrigen geltend gemachte "Verstoß gegen Bundesrecht" rechtfertigt keine Zulassung der Revision. Typischerweise handelt es sich dabei um einen Revisions- (vgl. § 137 Abs. 1 Nr. 1 VwGO) und nicht um einen Revisionszulassungsgrund. Darüber hinaus legt der Kläger nicht dar, welchen Verstoß im Einzelnen er meint. Daher kommt auch eine Auslegung des Vorbringens beispielsweise als Grundsatzrüge nicht in Betracht.
4. Die Entscheidung über die Kosten folgt aus § 154 Abs. 2 VwGO. Die Festsetzung des Wertes des Streitgegenstandes beruht auf § 13 Abs. 1 Satz 2 GKG.