Heh, I wonder what got your friend thinking of monkeys and cows...
I think that this is a very original idea. Not much cows are pirates, and not much monkeys have cows for friends.
I don't think that the red outlines are that bad actually, I didn't even notice them untill I read that you used it. I think it goes good with the quirky-ness of this picture. The shading and highlights are superb, and the color choice works for the characters. There is a few things you could work on though. The first thing that stood out was the outline on the cows right shoulder (our left). I don't think it fits in well with the roundness of the cow, and it just feels messy compared to the rest of the picture. I think you could make it look a bit more uniform and clean. Another thing that looks a bit wrong is the symbol on the cow's hat. I think it fills up too much of the hat, and is at sort-of the wrong angle. Maybe if you just fit the symbol into the non shaded part it would help. And one final thing I noticed, or didn't notice, until I zoomed in that is, is the anchors in the background; they match too much with the other bg color, and don't stand out enough.
Phew. Other than that stuff, I think this is an excelent piece, and could be worthy of its own cartoon show. Great work, and keep pixeling!