I had this problem when I reopened a project (which was developed on XCode 3.something on Leopard) after upgrading to Snow Leopard and XCode 3.2. Curious enough, it only affected some kinds of builds (emulator builds went fine, device ones gave me the error). And I have libxml2 at /usr/include, and it indeed contains libxml/tree.h.
Even the magic "Clean" did not work, but "Empty Caches..." under the "XCode" menu (between the Apple logo and File) did the trick (was that menu there in previous versions?). Beats me the reason, but after a clean there were no more complaints regarding libxml/tree.h