Is it possible to screen print this logo on a colored t-shirt? The screen printer I am working with says we can do gradients on a colored shirt but it won't print consistently or well. She advises changing the 4 colors to solid and screen printing that on a white background (the white cross is negative space).
What your printer told you is correct. Think of it like this: anywhere you see white in your image, you'll see shirt color instead. (Unless you pay for the addition of white ink, but with unfinished edges like you have there, it's not going to look great.)
Here's an image to help visualize what printing this on different colored shirts might look like: