tl;dr it only really slows down when >60% of the screen are water tiles but i have no idea how else i would implement them :S
Just to be sure, when you cycle through water images you're just updating a BufferedImage to point to another, pre-loaded BufferedImage, and not creating a new BufferedImage each time, right?
I couldn't be 100% sure from reading your original post, but are your water tiles created by drawing a translucent water image on top of another image? If so then I agree with appel that this is likely your problem, since translucent images most likely won't be accelerated. But if they're fully opaque then your problem is likely elsewhere.