I've booked lots of free flights both on SHA-HND (and vice versa) and PVG-NRT (as well as NRT-PVG). I've always found the SHA-HND flights to be slightly harder to book, but not impossible. SHA-HND has always been more popular due to their close distance from Shanghai and Tokyo respectively. So free seats are sometimes harder to get.
Sometimes I've had blackout dates on SHA-HND flight which UA said was because of ANA saying it was blacked out, other times they said it was just unavailable in economy (although business class seats were open). But then I called back a day or two later and suddenly seats opened up. So it could be that availability was just not there at that time and became available sometime later.