Thank you for the suggestions, Number_6!
I did indeed have segments left in Europe and so ended up booking LHR-LIS and the LIS-MAD-CDG segments as you suggested.
AA seem to have added a £5 service charge for changing tickets in the UK now, so I decided to go use BA to do the reissue as I was near their travel shop in Piccadilly. I suppose I can see why they charge so much for the change...the guy must have been typing in seemingly random strings of characters into his terminal for about half an hour before the new tickets popped out the printer. I also got charged a few extra pounds for taxes..and £3 for using a credit card!
Anyway, it all worked out fine. Thanks again for your help.
Regards,
Ben