Thanks for you answers. I finally found a solution that worked for me. It involves a class in ArcObjects that I never heard of: Cleaner. It has one method called release which allows you to release the locks on a single ArcObject, which is what I needed to do. It also has some shotgun methods to release all the objects in a thread, or all the objects in the process, but it cautions against using those unless you know that the thread is terminating, or the JVM is shutting down, respectively.
I'm not sure why I needed to manually release the lock, but doing so fixed my problem.
Anyway, here's the link to the JavaDoc for this class:
12/30/2011: I found that maintaining a Java HashSet of my ArcObjects made it easy to release any locks that were left behind. There's no penalty for attempting to release a lock that's already been released.