Aus den Erwägungen:
b) Nach Ueli Kieser (a.a.O. N 28 zu Art. 52) berücksichtigt der Grundsatz der Entschädigungslosigkeit des Einspracheverfahrens nicht, dass dieses Verfahren zwingend zu durchlaufen ist, bevor ein Beschwerdeverfahren eingeleitet werden kann. Er lasse ausser Acht, dass angesichts der verfahrensrechtlichen Schwierigkeiten, der materiellrechtlichen Problemstellungen und in Anbetracht der Bedeutung der Entscheide in vielen Fällen eine fachkundige Vertretung erforderlich sei. Deshalb wäre eine Regelung vorzuziehen gewesen, wonach im Einspracheverfahren ein Anspruch auf Parteientschädigung bestanden hätte. Der Gesetzgeber hat sich jedoch, wie erwähnt, für den Grundsatz der Entschädigungslosigkeit des Einspracheverfahrens entschieden (Art. 52 Abs. 3 ATSG).
c) Der Meinung von Kieser (a.a.O. N 28 zu Art. 52) ist beizupflichten, wonach die Stellung eines Gesuches um unentgeltliche Rechtspflege nicht unabdingbare Voraussetzung für die Ausrichtung einer Parteientschädigung bei Obsiegen im Einspracheverfahren ist. Bei Vorliegen besonderer Umstände, etwa bei ausserordentlichen Aufwendungen oder Schwierigkeiten, kann eine Parteientschädigung zugesprochen werden. Wäre dem anders, hätte der Gesetzestext entsprechend enger gefasst werden müssen. Der Wortlaut von Art. 52 Abs. 3 ATSG lässt hingegen Platz für weitere Ausnahmen. Dies entspricht denn auch beispielsweise der Praxis des Sozialversicherungsgerichts des Kantons Zürich (vgl. Urteile AL.2004.00495 vom 11.2.2005 E. 7.3 und AL.2007.00394 vom 31.7.2008 E. 6.3).
Bei der Frage, ob ein Verfahren besondere Schwierigkeiten mit sich bringt, rechtfertigt sich eine analoge Heranziehung der beim Anspruch auf unentgeltliche Verbeiständung nach Art. 37 Abs. 4 ATSG vorausgesetzten sachlichen Gebotenheit der Verbeiständung. In diesem Sinne gilt es die Umstände des Einzelfalls, die Eigenheiten der anwendbaren Verfahrensvorschriften sowie die Besonderheiten des jeweiligen Verfahrens zu berücksichtigen. Dabei fallen neben der Komplexität der Rechtsfragen und der Unübersichtlichkeit des Sachverhalts auch in der Person des Betroffenen liegende Gründe in Betracht, wie etwa seine Fähigkeit, sich im Verfahren zurechtzufinden. Falls ein besonders starker Eingriff in die Rechtsstellung des Bedürftigen droht, ist die Verbeiständung grundsätzlich geboten, andernfalls bloss, wenn zur relativen Schwere des Falls besondere tatsächliche oder rechtliche Schwierigkeiten hinzukommen, denen der Gesuchsteller auf sich alleine gestellt nicht gewachsen ist, und wenn auch eine Verbeiständung durch Verbandsvertreter, Fürsorger oder andere Fach- und Vertrauensleute sozialer Institutionen nicht in Betracht fällt (BG-Urteil 8C_18/2007 vom 1.2.2008 E. 5.1 mit Hinweisen).
a) Mit Schreiben vom 22. Februar 2007 eröffnete die Beschwerdegegnerin dem Beschwerdeführer, gemäss Mitteilung des Konkursamtes vom 20. Februar 2006 seien für das Jahr 2003 zu wenig Löhne deklariert worden, wodurch ihr ein Schaden von Fr. 3417.10 entstanden sei. Vor Erlass einer Schadenersatzverfügung habe der Beschwerdeführer Gelegenheit, dazu Stellung zu nehmen.
In seiner Stellungnahme vom 21. März 2007 hielt der Beschwerdeführer im Wesentlichen fest, die Beschwerdegegnerin sei am 20. Februar 2006 vom Fall in Kenntnis gesetzt worden. Am 22. Februar 2007 sei er von der Beschwerdegegnerin beschuldigt worden, einen Schaden verursacht zu haben. Die einjährige Verzögerung schränke seine Möglichkeit, den Sachverhalt nachzuvollziehen, stark ein. Die Anschuldigung sei sehr allgemein formuliert und verhindere zum Vornherein eine Überprüfung durch ihn, sofern er überhaupt zu den Akten komme. Der Konkursverwalter habe nie darüber informiert, dass etwas nicht korrekt abgelaufen wäre. Zusammenfassend hielt der Beschwerdeführer fest, dass er weder Beweisunterlagen noch Argumente vorbringen könne, welche ihn entlasten würden, da die Vorhaltungen so allgemein gehalten seien, dass diese für ihn weder überprüfbar noch nachvollziehbar seien.
Mit Schreiben vom 23. März 2007 teilte die Beschwerdegegnerin dem Beschwerdeführer mit, dass der Umstand der einjährigen Verzögerung tatsächlich als unglücklich zu bezeichnen sei. Allerdings müsse darauf hingewiesen werden, dass das Gesetz in einem solchen Fall eine Frist von bis zu zwei Jahren vorsehe. Dass der Nachtrag aus dem Jahr 2003 stamme, ändere nichts an der Tatsache, dass der Fall für die Beschwerdegegnerin erst am 20. Februar 2006 erkennbar geworden sei. Wie aus der beiliegenden Unterlage 1 hervorgehe, habe ihr das Konkursamt an diesem Datum mitgeteilt, dass für das Jahr 2003 noch Lohnforderungen offen seien, die in den Konkurs der A AG eingegeben worden seien. Die entsprechenden AHV-Beiträge seien mit Nachzahlungsverfügung vom 25. April 2006 in Rechnung gestellt worden. Die Forderung habe sich um Fr. 2652.45 reduziert (Zahlung der Arbeitnehmerbeiträge durch das Konkursamt). Der verbliebene Ausstand könne von der A AG nicht mehr eingefordert werden.
Dazu nahm der Beschwerdeführer mit Schreiben vom 4. April 2007 Stellung. Trotz den zusätzlichen Informationen und Unterlagen sei die Sache für ihn immer noch nicht vollständig überprüfbar und nachvollziehbar. So sei ihm beispielsweise nach wie vor nicht klar, aus welchem Grund B und C nachträglich noch Lohnforderungen geltend gemacht hätten. B sei in der Zeit vom 1. März bis 31. Mai 2003 weder bei der A AG angestellt gewesen noch habe er für die A AG irgendwelche Dienstleistungen erbracht oder Arbeiten verrichtet. C sei in der Zeit vom 1. Januar bis 31. Dezember 2003 bei der A AG angestellt gewesen. Der vereinbarte Lohn wie auch der ihm zustehende Bonus seien ihm ausbezahlt und die Sozialversicherungen korrekt abgewickelt worden. Die Lohnforderungen von B und C seien für ihn nicht nachvollziehbar und daher auch nicht berechtigt. Das Konkursamt habe ihn über diese Forderungen nie informiert. Er habe auch nie die Gelegenheit erhalten, dazu Stellung zu nehmen und sich zu äussern, ob diese Forderungen berechtigt seien oder nicht. Wenn der Konkursverwalter diese Forderungen zugelassen habe, so sei dies von ihm nicht beeinflussbar. Offenbar habe das Konkursamt diese Forderungen und auch die Arbeitnehmerbeiträge bezahlt. Weshalb das Konkursamt in diesem Fall nicht auch die Arbeitgeberbeiträge bezahlt habe, sei ihm nicht klar. Wenn die Konkursverwaltung diese Forderungen schon zulasse und gestützt darauf den Lohn ausbezahle, sei er der Meinung, dass die Konkursverwaltung auch für die Bezahlung der AHV-Beiträge verantwortlich sei. Die Lohnforderungen würden gemäss Angaben der Beschwerdegegnerin aus dem Jahr 2003 stammen. Es handle sich um Forderungen, die von B und C erst nachträglich im Konkurs eingereicht und die erst später von der Konkursverwaltung bezahlt worden seien. Vorher, speziell im Jahr 2003, seien diese Forderungen nie geltend gemacht worden. Es seien auch nie entsprechende Lohnabrechnungen erstellt worden. Die AHV-Beitragspflicht entstehe aber erst, wenn der Lohn ausbezahlt werde. Im Jahr 2003 habe folglich noch gar keine Beitragspflicht bestanden. Die Beitragspflicht sei vielmehr erst nach der Konkurseröffnung entstanden. Demzufolge könne man ihn für diese Beiträge mit Sicherheit nicht verantwortlich machen. Eine Haftung nach Art. 52 des Bundesgesetzes über die Alters- und Hinterlassenenversicherung (AHVG) setze eine Missachtung von Vorschriften voraus. Es sei nicht ersichtlich, welche (Abrechnungs-)Vorschriften er verletzt haben sollte. Nicht nur für die Beschwerdegegnerin, sondern auch für ihn sei der Fall erst nachträglich erkennbar geworden. Er habe bis zum Schreiben vom 22. Februar 2007 keinerlei Kenntnis von diesen Lohnforderungen gehabt. Demzufolge habe er auch überhaupt keine Möglichkeit gehabt, für die Ablieferung der AHV-Beiträge zu sorgen. Ein Organ hafte aber von vornhinein nur so lange, als es den Geschäftsgang beeinflussen könne. Wie man ihm unter diesen Umständen eine grobfahrlässige oder sogar vorsätzliche Verletzung der AHVG-Pflichten vorwerfen wolle, sei nicht nachvollziehbar. Ergänzend verweise er auf seine Stellungnahme vom 21. März 2007. Zusammenfassend könne man ihn für den Schaden der Beschwerdegegnerin nicht verantwortlich machen. Er beantrage daher, dass auf den Erlass einer Schadenersatzverfügung verzichtet werde.
Am 26. April 2007 erliess die Beschwerdegegnerin die Schadenersatzverfügung.
Dagegen liess der Beschwerdeführer, nunmehr vertreten durch einen Rechtsanwalt, am 23. Mai 2007 Einsprache erheben. Der Rechtsvertreter des Beschwerdeführers legte in seiner gut 16 Seiten umfassenden Einsprache dar, weshalb die Verfügung der Beschwerdegegnerin vom 26. April 2007 aus mehreren Gründen aufzuheben sei. Namentlich machte er geltend, die Schadenersatzforderung sei verjährt. Zudem sei der Beschwerdegegnerin gar kein Schaden entstanden, da die Lohnforderungen von B und C in keiner Art und Weise nachvollziehbar und daher auch nicht berechtigt seien. Im Weiteren seien die Lohnforderungen erst nachträglich im Konkursverfahren eingereicht und erst später von der Konkursverwaltung bezahlt worden. Zuvor, insbesondere im Jahr 2003, seien diese Forderungen nie geltend gemacht worden. Es seien auch nie entsprechende Lohnabrechnungen erstellt worden. Die Beitragspflicht sei erst nach der Konkurseröffnung entstanden und fällig geworden. Demzufolge könne der Beschwerdeführer aus zeitlichen Gründen nicht für diese Beiträge verantwortlich gemacht werden. Auch fehle es an einer Pflichtverletzung. Es sei nicht ersichtlich, inwiefern ein Organ eine Pflichtverletzung begangen haben sollte, wenn es für Löhne, die gar nicht ausgerichtet worden seien, keine Arbeitgeberbeiträge bezahlt habe. Es könne nicht darum gehen, dass ein Organ mit Bezug auf Löhne, die erst nach seinem Ausscheiden aus der Gesellschaft ausgerichtet würden, ebenfalls noch für die Bezahlung der Arbeitgeberbeiträge hafte. Die A AG habe im Jahr 2003 die geschuldeten Akontobeiträge geleistet. Das aus der Endabrechnung resultierende Guthaben der Ausgleichskasse sei ebenfalls beglichen worden. Schliesslich könne dem Beschwerdeführer auch kein Verschulden vorgeworfen werden. Die Ausgleichskasse habe nie auch nur eine ausstehende Zahlung gemahnt, geschweige denn einen Zahlungsbefehl verschicken müssen.
Mit Einspracheentscheid vom 25. Juni 2007 hiess die Beschwerdegegnerin die Einsprache des Beschwerdeführers ohne Zusprechung einer Parteientschädigung gut und hob die angefochtene Schadenersatzverfügung vom 26. April 2007 auf, da infolge der Vorbringen des Einsprechers und der aufgelegten Belege an der Schadenersatzverfügung nicht festgehalten werden könne.
b) Den gemachten Ausführungen kann entnommen werden, dass sich anlässlich des Verwaltungsverfahrens sowohl sachverhaltlich als auch rechtlich keinesfalls leicht oder ohne weiteres zu überblickende und zu beantwortende Fragen stellten, namentlich nicht für eine fachlich unkundige Person. So ist insbesondere hervorzuheben, dass sich der geltend gemachte Schadenersatzanspruch auf nachträglich im Konkurs eingebrachte Lohnforderungen aus dem Jahr 2003 stützte. Die Beschwerdegegnerin berief sich diesbezüglich lediglich auf die Anerkennung dieser Lohnforderungen durch das Konkursamt und legte folglich die Berechtigung der Schadenersatzforderung dem Beschwerdeführer nicht nachvollziehbar dar. Unter diesen Umständen konnte vom unkundigen Beschwerdeführer nicht leichthin erwartet werden, diesen aussergewöhnlichen Sachverhalt ohne fachliche Unterstützung zu überblicken, geschweige denn anschliessend daraus die korrekten rechtlichen Schlüsse zu ziehen. Die sachverhaltlichen und rechtlichen Schwierigkeiten zeigen sich im Weiteren darin, dass der Beschwerdegegnerin im nichtstreitigen Verwaltungsverfahren Fehler unterliefen, welche sie im rechtsmittelähnlichen Einspracheverfahren mit der Aufhebung der Schadenersatzverfügung vom 26. April 2007 korrigieren musste.
Dem Beschwerdeführer kann nicht vorgeworfen werden, er hätte sich persönlich zu wenig bemüht. In seiner ersten Eingabe vom 21. März 2007 war er noch nicht in der Lage, konkrete Einwendungen vorzubringen, da die Beschwerdegegnerin ihren Anspruch nicht nachvollziehbar dargelegt hat. Mit Schreiben vom 23. März 2007 lieferte sie dann weitere Informationen, worauf es dem Beschwerdeführer mit Eingabe vom 4. April 2007 möglich war, konkretere Einwendungen vorzubringen. Diese Einwendungen waren sachlich begründet und genügten den Erwartungen, die man an einen fachunkundigen Laien haben darf. Damit hat der Beschwerdeführer zwar gezeigt, dass er fähig ist, sich im Verfahren zurechtzufinden. Trotzdem reichten diese sachlichen Einwendungen nicht aus, eine Schadenersatzverfügung der Beschwerdegegnerin zu verhindern. Erst nachdem sich der Beschwerdeführer verbeiständen liess und der Rechtsvertreter eine Einsprache einreichte, reagierte die Beschwerdegegnerin und hob die Schadenersatzverfügung auf. Unter diesen Umständen ist die sachliche Gebotenheit der Verbeiständung offensichtlich. Im Weiteren ist die Verbeiständung grundsätzlich geboten, falls ein besonders starker Eingriff in die Rechtsstellung des Bedürftigen droht. Im vorliegenden Verfahren ging es im Gegensatz zum in der Praxis des Sozialversicherungsverfahrens überwiegenden Leistungsrecht um eine Schadenersatzforderung der Ausgleichskasse gegenüber dem Versicherten. Dabei kann durchaus gesagt werden, es handle sich um einen besonders starken Eingriff in die Rechtsstellung des Bürgers.
Die besonderen Schwierigkeiten im Verwaltungsverfahren führten schliesslich zu besonderen Aufwendungen. Nachdem die beiden Eingaben des Beschwerdeführers erfolglos blieben, legte dessen Rechtsvertreter in einer gut 16 Seiten umfassenden Einsprache ausführlich dar, weshalb die angefochtene Schadenersatzverfügung aufzuheben sei. Erst diese besonderen Aufwendungen führten letztlich zur Aufhebung der Schadenersatzverfügung durch die Beschwerdegegnerin.
Aus dem Verweis der Beschwerdegegnerin auf die höchstrichterliche Rechtsprechung, wonach sich im Einspracheverfahren eine anwaltliche Verbeiständung nur in Ausnahmefällen aufdränge, in denen ein Rechtsanwalt beigezogen werde, weil schwierige rechtliche oder tatsächliche Fragen dies notwendig erscheinen liessen und eine Verbeiständung durch Verbandsvertreter, Fürsorger oder andere Fach- und Vertrauensleute sozialer Institutionen nicht in Betracht falle, vermag sie nichts zu ihren Gunsten herzuleiten. Wie bereits dargelegt sind im vorliegenden Fall besondere Schwierigkeiten gegeben. Zudem ist nicht ersichtlich, an welche soziale Institution sich der Beschwerdeführer in vorliegendem Fall hätte wenden sollen, geschweige denn, was ein Fürsorger in vorliegendem Fall hätte bewirken können, ging es doch in materiellrechtlicher Hinsicht um eine Organhaftung nach Art. 52 AHVG.
Abschliessend ist darauf hinzuweisen, dass bis heute weder dem Beschwerdeführer noch dem Verwaltungsgericht mitgeteilt wurde, aus welchem Grund die Beschwerdegegnerin ihre Schadenersatzverfügung vom 26. April 2007 aufgehoben hat. Vielmehr beschränkte sich die Beschwerdegegnerin auf die pauschale Begründung, dass sie infolge der Vorbringen des Einsprechers und der aufgelegten Belege zum Schluss gelange, dass an der Schadenersatzverfügung nicht festgehalten werden könne.
In Anbetracht dieser besonderen Umstände würde es geradezu in verfassungsmässig unhaltbarer Weise dem Gebot der Gerechtigkeit widerlaufen, würde man vorliegend dem Beschwerdeführer für das Einspracheverfahren keine Parteientschädigung zusprechen (Art. 8 BV; offengelassen in BGE 117 V 401).
c) Nach dem Gesagten ist die Verwaltungsgerichtsbeschwerde gutzuheissen und dem Beschwerdeführer für das Einspracheverfahren eine Parteientschädigung zuzusprechen. Zur Festlegung des Quantitativs der Parteientschädigung ist die Sache an die Beschwerdegegnerin zurückzuweisen.