Here's my question: imagine a ball rolling towards a brick wall. It hits the brick wall, and stops. It has lost its kinetic energy, right? And change in kinetic energy is equal to Work. But work also relies upon force being applied over a distance. So what I'm thinking is that there has been a nonzero change in kinetic energy, but because no change in distance occurred, no work was done. But that would violate the idea that the change in kinetic energy doesn't equal the work done. How is that possible?

As nothing is perfectly rigid, as the ball strikes the wall it will deform. This deformation allows the wall to act through out a distance and thus preform work on the ball.

The work done in deformation creates heat in the object(s) that deformed.

Ah-HA! I get it. It reminds me of the deformation of a baseball on a bat...

 

http://webusers.npl.illinois.edu/~a-nathan/pob/pics/ballbat2.jpg