Hello,
Regarding new/existing, all elements (but not connectors) have a "Status" property, which can be searched for, reported on in documents, and used in diagram filters. Depending on how you pull information out of EA, the diagram filters may cover your needs.
The status can also be displayed directly in diagrams, but this really only works for requirement-style elements; for others the status is displayed in the element shadow on the diagram which is very hard to see.
The set of available statuses (Proposed, Implemented, etc) can also be modified as required. For more details, check the help file under Modeling Basics -- Reference Data -- General Types -- Status Types.
You can of course simply change the colour manually, but unless your model is minimal and will be thrown away, this isn't a good idea. The colour of a UML element is not intended to carry information, so EA does not treat it as a fundamental property of the element, which means you can't test for it in document generation etc.
The best alternative is to define your own stereotypes and write shape scripts which change the colour based on the status or on a tagged value you define, as qwerty suggests.
This is more work, but worth it if you're in a medium-to-large scale project.
HTH,
/Uffe