This seems very very familiar to https://jira.jboss.org/jira/browse/JBIDE-6024
Indeed it does. However, we did just encounter exactly the same problem deploying to a Tomcat instance using the WTP supplied server adapter. We added libs to our project, outside of WEB-INF/lib. Added them to the .classpath and marked them as web library dependencies.
After a redeploy, the new libs weren't deployed, but the old ones were. The simple close, open, redeploy cycle didn't help here. Eventually, after much trial and error suddenly the following seemed to fix the problem: close, open, remove deployment, clean, add deployment.