The answer from Xilinx (via email) is below. It makes no mention of multi-threading. It also references a their software tool 8.2i which was released in 2006 (6 years ago!!!). In short, it makes no sense.
Lessons learned:
- Xilinx support is terrible.
 
- Xilinx software tools are an afterthought for them.
 
- I can only assume that what is outlined in documentation is correct, specifically that you cannot use dynamic memory allocation in a multi-threaded environment. This means no c++ standard library containers.
 
- If you're the hardware guy about to select a MicroBlaze soft core processor, check with the firmware guy before you do that. What kind of applications is he expecting to write? Make sure he knows that he can't write a multi-threaded application in C++.
 
malloc()
Microblaze C library shipped with a small, minimal functionality
  malloc(). When used, memory could not be freed. Other functions such
  as calloc, realloc, etc., were not supported. There were also bugs
  when using both malloc() and routines such as printf, scanf, etc. To
  fix this, the minimal functionality malloc() has been removed. It has
  been replaced by original Newlib malloc(). As a result, you should see
  NO functionality issues. You might see a code size increase of around
  4K. Because of the differences in which the new full functionality
  malloc() requests memory, user programs might need to review their
  heap size settings. If you see your malloc() calls returning NULL,
  where they used to work, try increasing your heap size. This change
  was essential to fix broken functionality.
For the rare cases where you still want the original light-weight, but
  broken malloc() functionality, the source code (malloc.S) can be
  included as one of the source files to be compiled to build your
  application. This will retain the old functionality, code size
  requirements, and dynamic memory requirements seen prior to EDK 8.2i.
xil_malloc()
MicroBlaze C library shipped with an alternative implementation of
  dynamic memory allocation called xil_malloc(). This routine has some
  limitations; it does not allocate memory from the heap, but rather
  from a fixed 64K buffer. This routine has now been deprecated. Though
  this routine is still available for linkage, its use is strongly
  discouraged. Please use malloc(); it is smaller than xil_malloc() and
  provides better functionality. When using malloc(), make sure to
  review your heap size settings to satisfy your dynamic memory
  requirements.
The standalone BSP contains a parameter "need_xil_malloc". This
  parameter was intended to allow you to write code that contains
  malloc(), yet wire it to the xil_malloc() implementation. Due to bugs
  in the implementation of the parameter and due to the deprecation of
  xil_malloc(), this parameter is deprecated as well.
Xilkernel contains a parameter "use_xil_malloc". This parameter was
  intended to allow the kernel message queue implementations to use
  xil_malloc() instead of malloc(). Due to the deprecation of
  xil_malloc(), this parameter is deprecated as well.
If you still want xil_malloc() source code for legacy reasons, the
  "xil_malloc.c" and "xil_sbrk.c" files can be downloaded and used.
C++ Applications
Prior to EDK 8.2i C++ applications might exhibit unusual behavior,
  memory corruption, etc. To fix these issues, include the attached
  source file (newlib_malloc.c) as part of your application compilation.
  This will fix the unexplained crashes. This work-around fixes bugs in
  the malloc() implementation in the MicroBlaze C library. This
  work-around has been incorporated into the C library starting in EDK
  8.2i.
This information also appears to be available at: http://www.xilinx.com/support/answers/23345.html