Решил попробывать написать игру слова на Java, как мне решить проблему?
Вместо того, чтобы приводить весь класс, описали бы алгоритм. А вообще-то похоже, что у вас происходит вывод с нескольких потоков одновременно, отсюда и чехарда с буквами. Ну и существует такая весчь как дебаггер, доступный в любой IDE, даже в emacs, не говоря об эклипс, нетбинс и идеа. Просто прошагайте алгоритм и поставьте точки останова на непонятных местах.
Надеюсь это не домашнее задание. Вот вам упрощенный и  немного корявый вариант игры. Модифицируете его под свои нужды сами - просто лень сильно извращаться :)
И еще пара комментариев:  В Java принято имена переменных (за исключением констант)  и  методов писать с маленькой буквы. ИМХО Всегда блок if заключайте в скобки. Даже если это одна строчка кода.  package wordgame;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Game {

	public static void main(String[] args) {
		new Game().run();

	}

	private static final char[] VALID_CHARACTERS = new char[] { 'а', 'б', 'в',
			'г', 'д', 'е', 'ж', 'з', 'и', 'к', 'л', 'м', 'н', 'о', 'п', 'р',
			'с', 'т', 'у', 'ф', 'х', 'ц', 'ч', 'щ', 'э', 'ю', 'я' };
	
	private Set<String> words; 

	private int playerNumber;
	private Scanner scanner;
	private Character playerWordLastChar;

	public void run() {
		words =  new HashSet<String>();
		scanner = new Scanner(System.in, "cp1251");
		playerNumber = 1;
		System.out.println("Игра началась! \nВведите слово!\nДля подтверждения своего ответа нажмите \"ENTER\"");
		nextPlayerTurn();		
	}

	private void nextPlayerTurn() {
		System.out.println("\nХод игрока " + playerNumber + "\n");
		while (!submitTurn()) {
		}

		playerNumber = playerNumber == 1 ? 2 : 1;
		nextPlayerTurn();

	}

	private boolean submitTurn() {
		String word = scanner.nextLine();

		if (word.isEmpty()) {
			
			System.out.println("Введите слово!");
			return false;
			
		} 
		
		char firstChar = word.charAt(0);
		char lastChar = word.charAt(word.length() - 1);
		boolean submit = false;
		
		if(words.contains(word)) {
			
			System.out.println("Такое слово уже было!");
		}
		
		else if (playerWordLastChar != null && firstChar != playerWordLastChar) {
			
			System.out.println("Слово должно начинаться на \"" +  playerWordLastChar +"\"");
			
		} else if (!isLastCharValid(lastChar)) {
			
			System.out.println("Слово не должно оканчиваться на: \"" + lastChar+ "\"");
			
		} else {
			words.add(word);
			playerWordLastChar = lastChar;
			submit = true;
		}
		return submit;
	}

	private boolean isLastCharValid(char lastChar) {
		for (char ch : VALID_CHARACTERS) {
			if (ch == lastChar) {
				return true;
			}
		}
		return false;
	}

}
Еще раз повторюсь - код примитивный, но он должен натолкнуть вас в  правильном направлении.