Your web guys are correct, you will need to edit the cname record of one of the store domain names to be an alias of the the other domain name.

After the record is updated you will then need to update the HTTP_HOST value inside nopCommerce so that the system knows which store should be served to which domain name.