This is a known issue - basically the Travelocity booking engine does not show the same flight options as you would see in the GDS and no one is going to help you (or care) - for whatever reason, they filter flight availability without any rhyme or reason.

I tried to book HNL-KOA-LIH-HNL and found the specific flights I needed never showed up. I escalated to some pretty nasty US call center supervisors who frankly didn't give a damn, then I found the email for Travelocity Executive CS and sent them a livid email.

I suggest you start with your own livid email, then someone will get back with you. In my case, they were able to figure out their stupid booking engine would not show all the possible flights when booking HNL-KOA-LIH-HNL, but would if I booked HNL-KOA/LIH-HNL and then KOA-LIH nested as a separate ticket - so you're best bet is to play around with multi *ticket* options vs multi segment until you start seeing the flights you want.