Das von Keine Ahnung oben beschrieben Vorgehen halte ich auch für das beste.

Wird aus dem umtausch nichts, empfehle ich bei Reifenneukauf (generell) auf souveränen Pannenschutz (Schwalbe:HD-SpeedGuard/Double Defense; Conti: Vectran; Bontrager: Hard Case Light/Ultimate) und (bei hauptsächlicher Nutzung auf Asphalt) wenig Profil zu achten.
Infrage kommen da m.E. folgende Modelle:
[liste]
[*]Schwalbe Marathon Supreme*/Racer/Deluxe
[*]Bontrager H5 700C
[*]Conti Top Contact 2

*Mit dem Supreme hab' ich beste Erfahrungen gemacht, er summt allerdings.

Zu profilarmen Reifen allgemeinen ist zu sagen, dass sie in sehr ruppigem Gelände, besonders Matsch+Schnee nicht zu gebrauchen sind.