Struggling to refactor code to remove duplication
It seems like each method is iterating over the list of lines and doing something. It is the "doing something" that is unique. Consider having a single method that iterates over the lines and takes an interface to do the "something". For each method, an appropriate interface instance would be passed (possible anonymous inner class) that takes the appropriate action.

Something like this:

private interface ProcessLine{
     void processLine(String line, int index, int charIndex);
     void complete();
}

private ProcessLine process(ProcessLine processor){
  String text = textArea.getText();
  int start = 0;
  int count = 0;
  String buildNewTextArea = "";
  int index = 0;
  while (start &gt;= 0) {
    int nextLineStart = text.indexOf(NEW_LINE, start + NEW_LINE.length());
    if (nextLineStart == -1) {
        nextLineStart = text.length();
    }

    processor.processLine(line, count);
    index += buildNewTextArea.length();
    count++;
    start = text.indexOf(NEW_LINE, nextLineStart);
  }
  return processor;
}

private int getLineIndex(final int line) {
     int result = -1;
     return process(new ProcessLine(){
         public void processLine(String line, int index, int charIndex){
             if (index == line)
                 result = charIndex;
         }
     });
     return result;
}