There's only 1 daily Star Alliance flight from NRT to SHE (on ANA), and summer is a popular travel season. Unless you see award seats on ANA's own website, it's ANA that's holding back award seats.

If you're in PEK, try taking high speed rail to SHE. It's 3 hours 45 minutes and costs $40.