Sachverhalt:
A. Z._ ist Eigentümer der Liegenschaft Rebstockhalde xx, Grundstück Nr. 3543, Grundbuch (GB) Luzern, rechtes Ufer. Am 30. März 2009 reichte er bei der Stadt Luzern ein Baugesuch ein für den Abbruch des oberirdischen Teils des bestehenden Einfamilienhauses, das Erstellen eines zweigeschossigen Neubaus auf dem bestehenden Untergeschoss, bauliche Veränderungen im Untergeschoss und die Neugestaltung des Hauszugangs auf der Westseite. Das Bauprojekt lag vom 9. bis 28. April 2009 öffentlich zur Einsicht auf. Innert der Planauflagefrist erhoben die benachbarte Grundeigentümerin X._ (Rebstockhalde yy, Grundstück Nr. 3766, GB Luzern) und der mit ihr zusammen wohnende Y._ Einsprache gegen das Bauvorhaben. Mit Entscheid vom 19. August 2009 erteilte der Stadtrat von Luzern Z._ - unter verschiedenen Bedingungen und Auflagen - die Baubewilligung für das Bauprojekt. Die Einsprache wies der Stadtrat, soweit sie öffentlich-rechtliche Punkte betraf, im Sinne der Erwägungen ab; im privatrechtlichen Einsprachepunkt verwies er die Einsprecher an das Zivilgericht.
Die von X._ und Y._ am 11. September 2009 erhobene Verwaltungsgerichtsbeschwerde wies das Verwaltungsgericht des Kantons Luzern mit Urteil vom 8. Februar 2010 ab, soweit es darauf eintrat.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 12. März 2010 beantragen X._ und Y._, das Urteil des Verwaltungsgerichts sei aufzuheben, und die nachgesuchte Baubewilligung sei zu verweigern. Eventuell sei die Sache zur Neubeurteilung an das Verwaltungsgericht zurückzuweisen. Des Weiteren sei ihrer Beschwerde die aufschiebende Wirkung zu erteilen.
Z._, die Stadt Luzern und das Verwaltungsgericht des Kantons Luzern beantragen die Abweisung der Beschwerde.
Mit Verfügung vom 20. April 2010 hat der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung zuerkannt.

Erwägungen:
1. Angefochten ist ein kantonal letztinstanzlicher Entscheid (<ref-law>), der eine öffentlich-rechtliche Angelegenheit im Sinne von <ref-law> betrifft. Ein Ausschlussgrund gemäss <ref-law> liegt nicht vor. Beim angefochtenen Urteil handelt es sich um einen Endentscheid (<ref-law>). Die Beschwerdeführer haben am vorinstanzlichen Verfahren teilgenommen, sind als Nachbarn durch den angefochtenen Entscheid besonders berührt und haben ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung (<ref-law>). Die weiteren Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass, weshalb auf die Beschwerde grundsätzlich einzutreten ist. Soweit die Beschwerdeführer in ihrer Eingabe jedoch pauschal auf ihre Ausführungen vor der Vorinstanz verweisen, genügen sie den Begründungsanforderungen von <ref-law>, wonach die Begründung in der Beschwerdeschrift selbst zu erfolgen hat, nicht.
2. 2.1 Die Beschwerdeführer rügen vorab eine unrichtige Feststellung des rechtserheblichen Sachverhalts durch die Vorinstanz.
Sie machen geltend, der Bebauungsplan B 105 vom 12. Juli 1967 und der Gestaltungsplan G 182 vom 23. November 1961 seien - entgegen den Ausführungen im angefochtenen Urteil - für die baupolizeiliche Prüfung des strittigen Bauprojekts von Relevanz. Mit dem Bebauungsplan B 136 Würzenbach vom 17. Dezember 1998 seien die beiden Pläne B 105 und G 182 zwar rechtskräftig aufgehoben worden, diese seien jedoch im Rahmen von Art. 4 Abs. 5 des Bau- und Zonenreglements der Stadt Luzern vom 5. Mai 1994 (BZR) bzw. hinsichtlich der Zweckbestimmung der Volumenerhaltung als Auslegungshilfe weiterhin beachtlich. Dies ergebe sich daraus, dass sowohl der Bebauungsplan B 105 als auch weitere Bauvorschriften in Form von öffentlich-rechtlichen Eigentumsbeschränkungen für das Baugrundstück Nr. 3543 des Beschwerdegegners und für ihr Grundstück Nr. 3766 im Grundbuch eingetragen seien. Diese nicht gelöschten Anmerkungen nähmen an der Wirkung des öffentlichen Glaubens des Grundbuchs teil, weshalb sie sich als Grundeigentümer gestützt auf <ref-law> auf diese Eintragungen hätten verlassen dürfen.
2.2 Die Vorinstanz führt aus, das Baugrundstück Nr. 3543 des Beschwerdegegners liege in der Wohnzone 1 des Bebauungsplans B 136 Würzenbach. Dieser Plan sei am 17. Dezember 1998 vom Grossen Stadtrat von Luzern erlassen worden, welcher die dagegen gerichteten Einsprachen - darunter auch jene des heutigen Beschwerdeführers Y._ - abgewiesen habe. Mit dem Erlass des Bebauungsplans B 136 seien zugleich der Bebauungsplan B 105 und der Gestaltungsplan G 182 aufgehoben worden. Die Anmerkung öffentlich-rechtlicher Eigentumsbeschränkungen im Grundbuch habe lediglich deklaratorischen Charakter. Dass die Löschung der Anmerkung "Bebauungsplan und Bauvorschriften" im Grundbuch nicht erfolgt sei, ändere mithin nichts an der Tatsache, dass sowohl der Bebauungsplan B 105 und die dazugehörigen Bauvorschriften als auch der Gestaltungsplan G 182 rechtskräftig aufgehoben worden seien und keinerlei Rechtswirkung mehr entfalteten. Anmerkungen nähmen an der Wirkung des öffentlichen Glaubens des Grundbuchs nicht teil, weshalb Erwerber eines Grundstücks nicht auf den wirklichen Bestand eines angemerkten Rechtsverhältnisses vertrauen könnten. Massgebend seien vorliegend mit anderen Worten einzig die aktuell gültigen öffentlich-rechtlichen Bauvorschriften sowie der Bebauungsplan B 136 samt Bauvorschriften.
2.3 Die Anmerkung öffentlich-rechtlicher Eigentumsbeschränkungen im Grundbuch hat keine rechtsbegründende, sondern bloss deklaratorische Wirkung (BGE 111 la 182 E. 4; Urteil 1C_32/2007 vom 18. Oktober 2007 E. 2.4). Sie dient einzig der Information Dritter und damit der Rechtssicherheit. Insbesondere können die Kantone nicht bestimmen, dass der Anmerkung einer öffentlich-rechtlichen Eigentumsbeschränkung nach kantonalem Recht rechtsbegründende Wirkung zukommt (Jürg Schmid, in: Basler Kommentar, Zivilgesetzbuch II, 3. Aufl. 2007, N. 2 ff. zu Art. 962).
Gemäss der Bestimmung von <ref-law>, auf welche sich die Beschwerdeführer berufen, ist derjenige, der sich in gutem Glauben auf einen Eintrag im Grundbuch verlassen und daraufhin Eigentum oder andere dingliche Rechte erworben hat, in seinem Rechtserwerb geschützt. Anmerkungen nehmen an der Wirkung des öffentlichen Glaubens jedoch nicht teil. Der Erwerber eines Grundstücks kann somit weder auf den wirklichen Bestand eines angemerkten Rechtsverhältnisses vertrauen noch aus dem Fehlen einer Anmerkung auf den Nichtbestand eines anmerkungsfähigen Rechtsverhältnisses schliessen (vgl. zum Ganzen Jürg Schmid, Gedanken zum öffentlichen Glauben des Grundbuchs - Vom Sein und Schein im Immobiliarsachenrecht; in: ZBGR 90/2009 S. 111 ff.; Dieter Zobl, Grundbuchrecht, 2. Aufl. 2004; N. 339).
2.4 Die Ausführungen der Vorinstanz verletzen folglich kein Bundesrecht. Da Anmerkungen von öffentlich-rechtlichen Eigentumsbeschränkungen im Grundbuch keine konstitutive Wirkung zukommt und von der Wirkung des öffentlichen Glaubens des Grundbuchs nicht miterfasst werden, sind die Vorbringen der Beschwerdeführer nicht stichhaltig. Im Übrigen handelten diese ohnehin nicht gutgläubig, da ihnen aufgrund früherer Verfahren bekannt war, dass mit dem Bebauungsplan B 136 sowohl der Bebauungsplan B 105 vom 12. Juli 1967 als auch der Gestaltungsplan G 182 vom 23. November 1961 aufgehoben wurden. Zusammenfassend sind damit, wie im angefochtenen Urteil zutreffend betont wird, (einzig) die aktuell gültigen öffentlich-rechtlichen Vorschriften und Pläne massgebend, nämlich insbesondere der Bebauungsplan B 136 samt Bauvorschriften.
2.5 Ergänzend ist festzuhalten, dass im Grundbuch bei den Grundstücken Nrn. 3543 und 3766 der Bebauungsplan B 105 ohnehin nicht explizit angemerkt ist. Vielmehr sind unter dem Titel "Anmerkungen" ganz allgemein "Bebauungsplan und Bauvorschriften" verzeichnet. Ob nach dem Erlass des Bebauungsplans B 136 vom 17. Dezember 1998 eine Löschung der Anmerkung angebracht gewesen wäre, kann offen gelassen werden. Jedenfalls liegt entgegen der in der Beschwerde vertretenen Meinung keine willkürliche Anwendung der "Kann-Bestimmung" von § 211 Abs. 2 des Planungs- und Baugesetzes des Kantons Luzern (PBG/LU) vor, wonach die zuständige Behörde die öffentlich-rechtlichen Eigentumsbeschränkungen aufheben und im Grundbuch löschen lassen kann, wenn die Voraussetzungen dahingefallen sind.
3. Die Beschwerdeführer machen eine willkürliche Anwendung kantonalen und kommunalen Rechts geltend.
3.1 Sie bringen zunächst vor, das in Frage stehende Bauprojekt verletze angesichts der "Mehrhöhe" das Gebot der Eingliederung nach § 140 PBG/LU.
Gemäss § 140 Abs. 1 PBG/LU sind Bauten und Anlagen in die bauliche und landschaftliche Umgebung einzugliedern. Sie sind zu untersagen, wenn sie durch ihre Grösse, Proportion, Gestaltung, Bauart, Dachform oder Farbe das Orts- und Landschaftsbild beeinträchtigen.
Bei der Beurteilung der Eingliederung ist nicht auf ein subjektives ästhetisches Empfinden abzustellen, sondern es sind möglichst objektivierte Kriterien anzuwenden. Der kommunalen Baubehörde steht bei der Anwendung der Ästhetikklausel von § 140 PBG ein besonderer Beurteilungsspielraum zu.
Die Beschwerdeführer substanziieren ihre Behauptung, wonach sich der Teilneubau des Beschwerdegegners von der Umgebung abhebe, nicht näher. Hierdurch vermögen sie eine willkürliche Anwendung der Ästhetikklausel von § 140 Abs. 1 PBG nicht hinreichend darzutun.
3.2 Die Beschwerdeführer beanstanden zudem eine willkürliche Ermessensausübung bzw. eine Verletzung von Art. 4 Abs. 1 und 5 BZR an.
Nach Art. 4 BZR mit der Marginalie "Volumenerhaltung" darf in den Gebieten mit Volumenerhaltung bei Neubauten und Veränderungen an bestehenden Bauten das Ausmass des bestehenden oberirdischen Gebäudevolumens nicht überschritten werden. Die Geschosszahl richtet sich nach den benachbarten Bauten (Abs. 1). Bei unbebauten Grundstücken und bei Grundstücken, die im Vergleich zur Umgebung weniger dicht überbaut sind, legt der Stadtrat das zulässige Bauvolumen fest. Er berücksichtigt dabei die örtliche Situation sowie baurechtliche Gründe, die zu einer geringeren Dichte geführt haben. Gemäss dem Merkblatt zur Volumenerhaltung in der Stadt Luzern (erstinstanzliche Akten act. 2) wird aufgrund städtebaulicher Kriterien und nach Besichtigung der örtlichen Situation bestimmt, welche Grundstücke in die Vergleichsberechnung einbezogen werden.
Mit Volumenauskunft vom 12. Dezember 2008 stellte die Stadtplanung Luzern fest, die Überbauung auf dem Grundstück Nr. 3543 des Beschwerdegegners weise eine im durchschnittlichen Vergleich zur Umgebung höhere Dichte auf (erstinstanzliche Akten act. 3). Die Vorinstanz erachtet diese Ausführungen als plausibel und stellt im angefochtenen Urteil hierauf ab. Demgegenüber gehen die Beschwerdeführer davon aus, das Grundstück des Beschwerdegegners sei im Vergleich zu den umliegenden Liegenschaften weniger dicht bebaut. Die unterschiedliche Betrachtung ist darauf zurückzuführen, dass die Beschwerdeführer insgesamt sechs - statt bloss vier - Gebäude in ihre vergleichende Volumenberechnung einbeziehen. Sie legen indessen nicht substanziiert dar, inwiefern die Baubewilligungsbehörde den ihr bei der Auswahl der vergleichend zu berücksichtigenden Gebäude zukommenden Ermessensspielraum überschritten haben sollte. Eine willkürliche Anwendung des kommunalen Rechts ist nicht ersichtlich.
Da somit gemäss der Volumenberechnung der Baubewilligungsbehörde, welche von der Vorinstanz übernommen worden ist, das Grundstück Nr. 3543 des Beschwerdegegners bereits heute im Vergleich zur Umgebung dichter bebaut ist, gelangt Art. 4 Abs. 5 BZR nicht zur Anwendung. Gestützt auf Art. 4 Abs. 1 BZR ist ein Neubau vorliegend nur unter Beibehaltung des bestehenden Volumens gestattet. Das Bauvorhaben des Beschwerdegegners erfüllt diese Voraussetzung, was von den Beschwerdeführern im Übrigen auch nicht explizit in Frage gestellt wird.
4. Die Beschwerde ist damit abzuweisen, soweit darauf einzutreten ist. Infolge ihres Unterliegens sind die bundesgerichtlichen Kosten den Beschwerdeführern aufzuerlegen (Art. 66 Abs. 1 und 5 BGG). Die Beschwerdeführer haben dem Beschwerdegegner eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG), wofür sie solidarisch haften (<ref-law> i.V.m. <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2. Die Gerichtskosten von insgesamt Fr. 3'000.-- werden den Beschwerdeführern auferlegt.
3. Die Beschwerdeführer haben den Beschwerdegegner für das bundesgerichtliche Verfahren mit insgesamt Fr. 3'000.-- unter solidarischer Haftung zu entschädigen.
4. Dieses Urteil wird den Parteien, der Stadt Luzern und dem Verwaltungsgericht des Kantons Luzern, Verwaltungsrechtliche Abteilung, schriftlich mitgeteilt.
Lausanne, 21. Juni 2010
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Stohner