Booking can be changed for paper reward ticket, but it also depends on timing. I had it done as recent as November 2006.

When I booked the reward ticket, the AC agent explained that once the reward paper ticket was issued, change on the booking was allowed up to about 22 days ( I couldn't recall the exact number of day ) prior to departure. There is fee for the change.

My travel date was late December. In November I called Aeroplan office to change my booking on a TG flight, which was of course subject to seat availability. Then I brought the paper ticket to AC ticket counter in the airport and let them make correction on the ticket. I was charged two times, ending up paying about $ 85 in total.