It sounds like you didn't have a very good coach. My first coach wasn't very helpful, my second was amazing. Keep looking!

Open mic nights at your local bar are a great source of data. Approach people after their performance, compliment them, and ask them if they have a coach they'd be willing recommend.

Try recording yourself as you do karaoke. The external perspective and hearing it "in the mix" really helps you tune your performance.