I think anyone trying to help you will need more information. database optimization is a big subject.
How big is/are the table(s) you need to update? What does the actual SQL query look like (post the code).
are you sure there is a performance problem on the database side and not in the code? Do you have any tools that break down the database steps so you can see where it is taking too long? How did you decide which indexes are not being used, from an explain plan? Are you able to change the database around (denormalize) if needed?