This week's book giveaway is in the OCPJP forum. We're giving away four copies of OCA/OCP Java SE 7 Programmer I & II Study Guide and have Kathy Sierra & Bert Bates on-line! See this thread for details.
I haven't seen this problem. What kind of libraries are they, JDBC drivers?
Have you double checked that they have ".jar" extensions? Sometimes Windows hides file extensions for 'known' file types. Did you compare the checksums with the originals to make sure your jars haven't been corrupted?
Do any of the operations done by the classes in these libs need special permissions (access to shared resources on other machines)? Applications started as services are usually run under a different user.