I've not been to Kagoshima or Miyazaki, and I've only passed through Saga. Although I haven't been to Oita in a while, I wasn't all that impressed with Beppu. Yufuin's nice, but there're other nice onsens in Kyushu. It seems to me that Fukuoka, Nagasaki, Kumamoto and Kagoshima are where first-timers should focus on. In order to cover those areas in a whirlwind, I suppose you could do it in as little as 4 days / 3 nights. If you wanted to cover it thoroughly, well then there's really no upper limit.

Fukuoka is an awesome big city with great food. I could spend a week there, I could live there. On the other hand, one can make the argument to skip Fukuoka altogether if you want to explore as much of Kyushu as possible in a limited amount of time.

Nagasaki is almost a can't-miss, but personally I don't think you need more than a day to explore the city itself. However, there's a few nice day trip options from Nagasaki. Kumamoto city and the Aso area are great, but I also don't know how the earthquake has impacted the area. ltfly seems to indicate one can still have fun there but it's not the same.

If you decide to skip Kumamoto, you could think about using 2 or 3 of Fukuoka/Nagasaki/Kagoshima as your bases, perhaps replacing 1 night for a stay in an onsen hotel such as at Kirishima, Unzen or Kurokawa. On the other hand, if you're not necessarily looking for a comprehensive tour of Kyushu, then you could spend all your nights in Fukuoka with maybe day trips to Nagasaki and Dazaifu. I've never been to Kirishima, Kurokawa or Kagoshima btw, so my rec for those places is based merely on the research I've done for our Kyushu trip this winter.

I think I did a day trip from Fukuoka the first time we did Nagasaki. Nagasaki is a memorable place in a pretty setting, but personally I think it can easily be covered in a day, esp if you're not doing the atomic bomb area. But abmj-jr thinks otherwise, and I'm sure there're others that would agree with him. And if you're interested in Shimabara/Unzen, Haus ten Bos (if you're into that type of stuff), Kujuuku-jima cruises, etc, then you should definitely set up base in Nagasaki.