Sachverhalt: A. Am 5. Dezember 2007 wurde in der Betreibung Nr. 1 des Betreibungsamts Region Solothurn dem Schuldner X._ (nachfolgend: Beschwerdeführer) der Zahlungsbefehl zugestellt. Er nahm diesen auf der Poststelle B._ in Empfang. Auf dem Schuldnerexemplar des Zahlungsbefehls befindet sich in der für die Erhebung des Rechtsvorschlags vorgesehenen Rubrik die Unterschrift des Schuldners, nicht aber auf dem Gläubigerdoppel. Das Dokument wurde an das Betreibungsamt weitergeleitet und von der "Amtschreiberei Region Solothurn, i. A. Y._" (Stempelaufdruck) wurde der Vermerk "kein Rechtsvorschlag" (Stempelaufdruck) angebracht. Z._ (nachfolgend: Beschwerdegegner) stellte am 22. Januar 2008 das Fortsetzungsbegehren, und am 30. Januar 2008 erhielt der Schuldner die Pfändungsankündigung. Mit Beschwerde vom 31. Januar 2008 an die Aufsichtsbehörde für Schuldbetreibung und Konkurs machte X._ geltend, er habe am 5. Dezember 2007 Rechtsvorschlag erhoben. Er stützte sich dabei auf die Erklärung der Postbeamtin W._ vom 31. Januar 2008, wonach der Schuldner am 5. Dezember 2007 um 15.00 Uhr Rechtsvorschlag verlangt und dies mit seiner Unterschrift bestätigt habe. Am 19. Februar 2008 verfügte die Amtschreiberei Region Solothurn bzw. das Betreibungsamt Region Solothurn, der Rechtsvorschlag von X._ in der Betreibung Nr. 1 werde nachträglich als gültig anerkannt. Die vom Beschwerdegegner dagegen bei der Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn eingereichte Beschwerde wurde mit Urteil vom 22. April 2008 gutgeheissen, die Verfügung des Betreibungsamts Region Solothurn vom 19. Februar 2008 aufgehoben und das Betreibungsamt angewiesen, dem Fortsetzungsbegehren des Beschwerdegegners stattzugeben. B. Der Beschwerdeführer (nun durch einen Anwalt vertreten) hat am 9. Mai 2008 beim Bundesgericht Beschwerde eingereicht. Er beantragt, das Urteil der Aufsichtsbehörde und die Pfändungsankündigung vom 25. Januar 2005 seien aufzuheben, und das Betreibungsamt Region Solothurn sei anzuweisen, den Rechtsvorschlag in der Betreibung Nr. 1 zu protokollieren. Mit Präsidialverfügung vom 30. Mai 2008 wurde der Beschwerde aufschiebende Wirkung zuerkannt. Die Aufsichtsbehörde für Schuldbetreibung und Konkurs beantragt in ihrer Vernehmlassung Gutheissung und der Beschwerdegegner in seiner Beschwerdeantwort Nichteintreten auf die Beschwerde, eventualiter abweisen, soweit darauf einzutreten sei.