What works. You need to include the JAR in the MANIFEST.MF file: when using the MANIFEST editor from Eclipse, navigate to tab “Plugin”, section “classpath”, and add the JAR there. And, if you want to have these JARs accessible from other plugins, add the corresponding packages to section “exported packages”.
What does not work. If you however just right-click the JAR file in package explorer and chose “Add to Build path” and (in case the JARs shall be accessible from other plugins) tick the JAR file in “Configure Build Path > Order and Export”, these changes get lost when using “PDE tools > Update classpath…”.
Explanation. As a general rule, the PDE mechanisms are a layer above the “normal” Java build path mechanism, i.e. simply use the higher level exclusively and you stay out of problems. The “PDE Tools > Update classpath” means probably: update the Java classpath (=Java build path) from the plugin’s classparth (= OSGi BundleClasspath in MANIFEST.MF, edited as described above); i.e. it’s the penetration of changes from PDE to (lower) Java abstraction level.