I dated a vegetarian for a year in Spain (although I know you said you aren't one), but here are some places to try in Madrid that serve chicken, beef, and meatless items:

-Gino's (Italian food..pasta, etc.)
-TGIFriday's (granted, very american, but it was my salvation for chicken) in Madrid next to the soccer statium for Real Madrid
-Hard Rock Cafe (again, american, sorry!) in Madrid near Plaza Colon
-Vips (hamburgers, pasta, all sorts of things)
-this chain-bar, which starts with a C, who's name I cannot remember at 3 in the morning (somebody help me out here), but there is always a plastic guy standing on top of a keg with a foaming beer in his hand in front of the bar - anyhow, they have great tapas like potatoes and cheese sticks

Also, I guess it is my experience that when I asked servers to leave out the meat, they usually didn't. I also found that some of the Chinese resteraunts are good and that Mexican resteraunts are great.

Good luck!

PS Is the name of the bar Cruz Campo? Anyone?