It seems like what I want is something that WordPress's internal permalink code isn't prepared to deal with. After reading this writeup by Otto, I've come to understand that having my permalinks start with %category% could create a performance issue down the road and I would have to create a function that further alters the WordPress permalink rules in order to get the attachment permalinks working with %category%.
As a result, I've decided to start all my posts with the year. This allows me to use the solution found here for attachment permalinks, and I'll avoid performance headaches in the future.
