We just booked a 3 week trip to Japan from March 23-April 13 2017. It's so far out that I didn't expect to have any difficulty finding rooms in our base cities of Tokyo, Kyoto and Kumamoto. But everything seems to be sold out! Does this seem to be correct or am I maybe trying to book too far out?
You're trying to book too far out. Many Japanese hotels, especially those not associated with Western chains, only accept bookings for the current and following quarter, meaning rooms for April 2017 may not be released until January 2017.
That said, cherry blossom season is busy, so booking in advance is advisable. If there's a particular hotel you're desperate to stay in, contacting them directly via email or phone may be an option.
As jpatokal said, you usually cant't book so much ahead of time, this year in some ryokan it's owner told me that the earliest you could book a room was three months in advance. I don't know if these three months are for every other hotel or the time in which you can book a room varies from hotel to hotel.
You could always use Airbnb japan: http://airbnb.jp/ in order to stay in some houses instead of hotels. As you speak with the owner directly there is no date limit where you can book your stay. I used it this summer and it was great.