Arduino 1.0 has introduced support for new and delete, but, unfortunately, only 1/6 part of required operators are implemented. Another problem is that this 1/6 part does not conform to the C++ standard and leads to undefined behavior in case if you run out of RAM.
There is uClibc++ posrt to arduino which has proper implementation for all required overloads for operator new and delete. But it conflicts with arduino library because both define implementation for the most commonly used operator new(size_t numBytes). You can take it here:https://github.com/kibergus/StandardCplusplus
In my opinion ideal solution would be to include STL implementation in arduino project. If you find this not feasible, please resolve conflict with uClibc++ library by either removing incomplete and incorrect realization of operator new and operator delete or by providing correct one (so I would be able to disable it in uClibc++). I would prefer if standard library will not be teared apart.
One of possible solutions:https://github.com/arduino/Arduino/pull/108
Here is a description how operator new should handle situation, when malloc returned 0:http://kibergus.su/en/node/92