Assuming that your module is configured properly, you may be having another problem. Are you sure that you are seeing "ClassNotFoundException", as opposed to "NoClassDefFoundError"? A lot of times, a "NoClassDefFoundError" is thrown if an exception occurs in static initialization. Is the class that's in the module doing any sort of static initialization?
It's difficult to really diagnose the problem. If you could provide log files, the contents of your module.xml, etc., somebody may be able to spot something that you didn't get quite right.
I would ask if you are launching wildfly with the "standalone-full.bat" script, but if you tried to add the module dependency to the deployed jar's MANIFEST.MF file, then it wouldn't really matter.