UART Transmitter Sends Bytes Out of Order

There isn't quite enough here to go on, but I'll hazard a guess. The code for uart1 is critical.

I'd test without repeated byte values - might make it slightly more obvious what is going on.

In the first piece of code (the not working one) in SEND_BYTES state you wrote:

@Cris72: No, it's not a typo - it's called part-select - added to the language in Verilog 2001. Your version would be simpler, except that it isn't allowed. One of the indices in the part-select must be a constant/literal and the other may be a variable - but they can't both contain variables.

module uart(
    input clk, // The master clock for this module
    input rst, // Synchronous reset.
    input rx, // Incoming serial line
    output tx, // Outgoing serial line
    input transmit, // Signal to transmit
    input  tx_byte, // Byte to transmit
    output received, // Indicated that a byte has been received.
    output  rx_byte, // Byte received
    output is_receiving, // Low when receive line is idle.
    output is_transmitting, // Low when transmit line is idle.
    output recv_error // Indicates error in receiving packet.
    );
parameter CLOCK_DIVIDE = 1302; // clock rate (50Mhz) / (baud rate (9600) * 4)
// States for the receiving state machine.
// These are just constants, not parameters to override.
parameter RX_IDLE = 0;
parameter RX_CHECK_START = 1;
parameter RX_READ_BITS = 2;
parameter RX_CHECK_STOP = 3;
parameter RX_DELAY_RESTART = 4;
parameter RX_ERROR = 5;
parameter RX_RECEIVED = 6;
// States for the transmitting state machine.
// Constants - do not override.
parameter TX_IDLE = 0;
parameter TX_SENDING = 1;
parameter TX_DELAY_RESTART = 2;
reg  rx_clk_divider = CLOCK_DIVIDE;
reg  tx_clk_divider = CLOCK_DIVIDE;
reg  recv_state = RX_IDLE;
reg  rx_countdown;
reg  rx_bits_remaining;
reg  rx_data;
reg tx_out = 1'b1;
reg  tx_state = TX_IDLE;
reg  tx_countdown;
reg  tx_bits_remaining;
reg  tx_data;
assign received = recv_state == RX_RECEIVED;
assign recv_error = recv_state == RX_ERROR;
assign is_receiving = recv_state != RX_IDLE;
assign rx_byte = rx_data;
assign tx = tx_out;
assign is_transmitting = tx_state != TX_IDLE;
always @(posedge clk) begin
    if (rst) begin
        recv_state = RX_IDLE;
        tx_state = TX_IDLE;
    end
    
    // The clk_divider counter counts down from
    // the CLOCK_DIVIDE constant. Whenever it
    // reaches 0, 1/16 of the bit period has elapsed.
   // Countdown timers for the receiving and transmitting
    // state machines are decremented.
    rx_clk_divider = rx_clk_divider - 1;
    if (!rx_clk_divider) begin
        rx_clk_divider = CLOCK_DIVIDE;
        rx_countdown = rx_countdown - 1;
    end
    tx_clk_divider = tx_clk_divider - 1;
    if (!tx_clk_divider) begin
        tx_clk_divider = CLOCK_DIVIDE;
        tx_countdown = tx_countdown - 1;
    end
    
    // Receive state machine
    case (recv_state)
        RX_IDLE: begin
            // A low pulse on the receive line indicates the
            // start of data.
            if (!rx) begin
                // Wait half the period - should resume in the
                // middle of this first pulse.
                rx_clk_divider = CLOCK_DIVIDE;
                rx_countdown = 2;
                recv_state = RX_CHECK_START;
            end
        end
        RX_CHECK_START: begin
            if (!rx_countdown) begin
                // Check the pulse is still there
                if (!rx) begin
                    // Pulse still there - good
                    // Wait the bit period to resume half-way
                    // through the first bit.
                    rx_countdown = 4;
                    rx_bits_remaining = 8;
                    recv_state = RX_READ_BITS;
                end else begin
                    // Pulse lasted less than half the period -
                    // not a valid transmission.
                    recv_state = RX_ERROR;
                end
            end
        end
        RX_READ_BITS: begin
            if (!rx_countdown) begin
                // Should be half-way through a bit pulse here.
                // Read this bit in, wait for the next if we
                // have more to get.
                rx_data = {rx, rx_data};
                rx_countdown = 4;
                rx_bits_remaining = rx_bits_remaining - 1;
                recv_state = rx_bits_remaining ? RX_READ_BITS : RX_CHECK_STOP;
            end
        end
        RX_CHECK_STOP: begin
            if (!rx_countdown) begin
                // Should resume half-way through the stop bit
                // This should be high - if not, reject the
                // transmission and signal an error.
                recv_state = rx ? RX_RECEIVED : RX_ERROR;
            end
        end
        RX_DELAY_RESTART: begin
            // Waits a set number of cycles before accepting
            // another transmission.
            recv_state = rx_countdown ? RX_DELAY_RESTART : RX_IDLE;
        end
        RX_ERROR: begin
            // There was an error receiving.
            // Raises the recv_error flag for one clock
            // cycle while in this state and then waits
            // 2 bit periods before accepting another
            // transmission.
            rx_countdown = 8;
            recv_state = RX_DELAY_RESTART;
        end
        RX_RECEIVED: begin
            // Successfully received a byte.
            // Raises the received flag for one clock
            // cycle while in this state.
            recv_state = RX_IDLE;
        end
    endcase
    
    // Transmit state machine
    case (tx_state)
        TX_IDLE: begin
            if (transmit) begin
                // If the transmit flag is raised in the idle
                // state, start transmitting the current content
                // of the tx_byte input.
                tx_data = tx_byte;
                // Send the initial, low pulse of 1 bit period
                // to signal the start, followed by the data
                tx_clk_divider = CLOCK_DIVIDE;
                tx_countdown = 4;
                tx_out = 0;
                tx_bits_remaining = 8;
                tx_state = TX_SENDING;
            end
        end
        TX_SENDING: begin
            if (!tx_countdown) begin
                if (tx_bits_remaining) begin
                    tx_bits_remaining = tx_bits_remaining - 1;
                    tx_out = tx_data;
                    tx_data = {1'b0, tx_data};
                    tx_countdown = 4;
                    tx_state = TX_SENDING;
                end else begin
                    // Set delay to send out 2 stop bits.
                    tx_out = 1;
                    tx_countdown = 8;
                    tx_state = TX_DELAY_RESTART;
                end
            end
        end
        TX_DELAY_RESTART: begin
            // Wait until tx_countdown reaches the end before
            // we send another transmission. This covers the
            // "stop bit" delay.
            tx_state = tx_countdown ? TX_DELAY_RESTART : TX_IDLE;
        end
    endcase
end
endmodule

As an alternative, I also tried removing the "catch-all" state for sending all 8 bytes and created a separate state for each byte that needed to be sent.

module transmission_test_3(sysclk, rxd, txd, LED, button);
input sysclk, rxd, button;
output txd;
output reg LED;
wire receiving_complete, isReceiving, isTransmitting, isError, reset;
reg begin_transmit;
reg  tbyte;
wire  rbyte;
reg  state = 4'b0;
reg  plain_text = 64'h0;
uart uart1(
    .clk(sysclk),
    .rst(reset),
    .rx(rxd),
    .tx(txd),
    .transmit(begin_transmit),
    .tx_byte(tbyte),
    .received(receiving_complete),
    .rx_byte(rbyte),
    .is_receiving(isReceiving), 
    .is_transmitting(isTransmitting),
    .recv_error(isError)
    );
always @(posedge sysclk)
    begin
        begin_transmit = 1'b0;
        case(state)
        4'b0000: begin
            if(button==1'b0) begin
                LED = 1'b1;
                plain_text = 64'hDEADBEEFAAABACAD;
                state = 4'b0001;
            end else begin
                LED = 1'b0;
            end
        end
        4'b0001: begin
            tbyte = plain_text;
            begin_transmit = 1'b1;
            state = 4'b0010;
        end
        4'b0010: begin
            if(!isTransmitting) begin
                tbyte = plain_text;
                begin_transmit = 1'b1;
                state = 4'b0011;
            end
        end
        4'b0011: begin
                if(!isTransmitting) begin
                    tbyte = plain_text;
                    begin_transmit = 1'b1;
                    state = 4'b0100;
                end
            end
        4'b0100: begin
            if(!isTransmitting) begin
                tbyte = plain_text;
                begin_transmit = 1'b1;
                state = 4'b0101;
            end
        end
        4'b0101: begin
            if(!isTransmitting) begin
                tbyte = plain_text;
                begin_transmit = 1'b1;
                state = 4'b0110;
            end
        end
        4'b0110: begin
            if(!isTransmitting) begin
                tbyte = plain_text;
                begin_transmit = 1'b1;
                state = 4'b0111;
            end
        end
        4'b0111: begin
            if(!isTransmitting) begin
                tbyte = plain_text;
                begin_transmit = 1'b1;
                state = 4'b1000;
            end
        end
        4'b1000: begin
            if(!isTransmitting) begin
                tbyte = plain_text;
                begin_transmit = 1'b1;
                state = 4'b0000;
            end
        end
        endcase
    end
endmodule

Quite cleary isTransmitting is active for 2 clocks.

Here is a version of your code that I modified somewhat and it works quite well. I'm using HyperTerm at 9600 8-N-2 to display the xmitted chars. Note the order in which 'plain_text' is read. For valid printing chars to be displayed you cannot send 0xDEADBEEF but rather its ASCII equivalent. There are some additional little changes, for example, tbyte = plain_text[(byteN*8)-1 -: 8] and the state machine runs at 4-KHz. No changes to uart.v except for some cosmetics.

FWIW HyperTerm is a bad choice of program, it is designed(?) to talk to modems and can get confused if the modem signal lines are incorrect.