I schedule a minimum 1-hour layover for domestic flights and 2 hours for international- I don't care what the airlines' computers allow. It's also possible that you fly into one EWR terminal and leave from another- last I was there (a year ago) CO Operated out of 2 terminals. At the time, only flights to a few cities left out of Termonal A and LAS wasn't one of them but that may have changed.

Definitely get them to re-accommodate you.