what can be used instead of new[]?

There is a known bug in free:

http://code.google.com/p/arduino/issues/detail?id=857

Various threads discuss a minor change to fix it. However since the bug is not in the "source" part of the libraries, but the supplied pre-compiled part, it isn't quite as trivial for the end-user to fix it on their own.

Some of the other Arduino-like boards (I forget which exactly) are supplied with the fixed library.