It's in version 1.7.2 (can't find it in the list).
When using default org.apache.velocity.app.VelocityEngine (Velocity 1.7) it's trying to create a new PatternLayout in it's LOG4J logger but it's using the constructor which takes a String and this constructor is not provider by log4j-over-slf4j.
It used to "work" well when there was no PatternLayout at all because Velocity catch NoClassDefFoundError but it does not expect a NoSuchMethodError.
The workaround (and what should be done anyway) is to provide a SLF4J based custom logger to Velocity. But still it would be nice to mimic a bit better log4j for this use case.