The simple way to troubleshoot it is to run a long wire from a known good ground and touch it to the brass base of the bulb. If the lights work normally, you've found the problem. The permanent fix is to run a heavy ground wire from the bed to the frame, and make sure the taillight assemblies are well-grounded to the bed.
Jerry
I had almost exactly the same problem as you when I bout my truck and was told this very same thing, grounding to the box was my problem.
