Sounds like your colleagues got a little lost in assumptions without thinking about what the purpose of a wireframe is. Let's start with a loose definition provided by Wikipedia:
A website wireframe (also "web wire
frame", "web wireframe", "web
wireframing") is a basic visual guide
used in interface design to suggest
the structure of a website and
relationships between its pages. A
webpage wireframe is a similar
illustration of the layout of
fundamental elements in the interface.
Typically, wireframes are completed
before any artwork is developed.
As with any word or term, it's important to consider what it really means. A wire-frame model is a term used in 3D modeling when talking about the representation of the physical structure of a polygonal model, which is rendered by showing connecting points between vertices. What's the point of a wire-frame model? It's to show the "guts" of a structure so as to better understand its composition.
When carried over to website wireframing as Wikipedia discusses it, we should consider how that meaning applies, and Wikipedia's definition nails it: "a basic visual guide used to suggest the structure of a website and relationships between its pages".
As you can tell, there's no mention of colour or how that visual guide should look. All that matters is that it suggests how the structure of the web site works. As long as it achieves that, it's an effective wireframe. So, for instance, these are all "valid" wireframes:
- sketches on a napkin
- sketches in 37signals' Draft or some other app on iPad
- sketchy looking wireframes made using a tool like Balsamiq Mockups
- tighter looking wireframes made using something like Axure or Illustrator
- lightweight designs of a site made in Photoshop, where the structure of the page is made apparent while including elements of design where relevant
- HTML exportable designs in Fireworks that allow you to see what elements a page consists of
- fully interactive HTML/CSS wireframes
It's just a matter of fidelity and detail. Perhaps you should make clear what kind of fidelity is expected in the deliverable and guide your designers along that path. But it's not a matter of "should color be used in a wireframe" - if color helps communicate the structure of the site, then absolutely color should be used in a wireframe!