I just did Kona in Nov. and I used Big Island Divers. 1 808 329 6068 They were AWESOME. They also have a nice web sight. I was going to take some gear but they have everything and it is new so I just took my computer. The whole Kona coast is a dive sight really but Big Island will send you to the good beach sights also.
I did go to a couple other dive shops got no service. I will not say their names cause anyone can have a bad day. The staff at Big Island really made my vacation.