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.