I guess this should do the trick
(Assume that the variable YESNO exists and is 1 Yes, 2 No)
string LabelVar (A60).
if LabelVar="No" LabelVar="Maybe".
autorecode LabelVar /into YESMAYBE.
you can of course do more complex things with the value labels, using the appropriate string functions.
Note that this often will not retain the original order of your values, though. If that is important you probably need to use Python.