Warren,
Try checking if there are duplicate values in your primary keys. Suggest you use regular indexes instead of primary.
Other things to look at include the triggers (if any) that you're using, I once had a bout of index problems because my table triggers were taking a long time to execute.
Use the coverage profiler to check how long does a particular record needs to take to update for tables that frequently have index corruption problems.
What's the actual problem that you're having that makes you conclude that its an index problem?
Maybe it could be network issues and not indexes.
HTH
Yau