When you rely on a weapon, you lose your edge. You're depending too much on the advantage the weapon gives you and ignoring everything else.
That aside, Kisame must have had great chakra to get Samehada to stay with him, so we know Kisame was tough without the sword. But he just fought, single-handedly (not counting the sword), the guy who controls the 8-tailed beast, and won. He outdid Sasuke and his entire crew. If the Raikage hadn't shown up, and if Samehada hadn't forsaken him, he would have successfully captured the 8-tails. I think that proves that he was an amazing fighter and deserving of everything that was said about him. He might even had been able to take on both Killer Bee and the Raikage, and win, if he had been fighting both of them from the start, before Samehada decided to be a little bitch.
I wonder what's going to happen to it now. Will Bee take it and become even more powerful? I gotta admit, I really like the idea of that. Will he absorb the sword and became a shark with 8, uh, tails? No. 8 heads? That'd be nice. Maybe a shark with 8 arms, that'd be boss.