Most likely you have both versions of libxml (1.8.x and 2.x) installed and for some reason gcc gives precedence to 1.8.x includes which are not compatible with 2.x includes.
You can verify this by doing:
On my system it returns the following (abridged for clarity):
[nsadmin@rusty nsxml]$ locate xmlmemory.h
This is not obvious, but /usr/include/libxml/xmlmemory.h is for 1.8.x version and /usr/local/include/libxml/xmlmemory.h is for 2.x. Your problem is that gcc tries to include from /usr/include and not /usr/local/include. From the top of my head I don't know how to force gcc to do otherwise (I'm sure it's somewhere in the gcc docs).
My first suggestion is to modify the Makefile and add the line:
CFLAGS = -I/usr/local/include
(note that on your system it can be somewhere else than /usr/local/include).
My second suggestion: get the tarball and compile from it. This is how I installed libxml on my RH 62 machine and it seems to be working.
If it fails - dive into gcc docs to find out how to force the proper include order.