Not sure if this is a clue, but almost every time the backup takes a long time or doesn't start, the transaction log backup immediately preceeding it takes a long time. Don't know if that's a cause, symptom, or coincidence.