Почему функция неправильно изменяет динамический массив?

Думаю, так будет нагляднее.

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

typedef char *STRING;
typedef STRING *STRING_ARRAY;

void test(STRING_ARRAY *parray){
    STRING_ARRAY array;
    array = malloc(sizeof(char*));
    array[0] = malloc(255 * sizeof(char));
    strcpy(array[0], "Hello world!");
    *parray = array;
}

void free_all(STRING_ARRAY *parray) {
    STRING_ARRAY array;
    array = *parray;
    free(array[0]);
    free(array);
    *parray = NULL; 
}

int main() {
    STRING_ARRAY array;
    test(&array);
    puts(array[0]);
    free_all(&array);
    return 0;
}

Почему функция неправильно изменяет динамический массив?

Читать классику Керниган и Ритчи "Язык программирования Си". Но если само понятие указателя вызывает сложности, то браться за Си рановато. Попробуйте Паскаль (Free Pascal и любой учебник, хотя бы книги доцента Столярова). Потренироваться с динамическими структурами вроде списков, деревьев и т.д. и уже затем возвращаться к Си. Я его учил в детстве после Паскаля и Ассемблера, поэтому быстро освоился, только с синтаксисом (местами запутанным) пришлось разобраться.

В вашем примере баг следующий - вы передаете в функцию test из main параметр типа "указатель на указатель". Передаете по значению, Си иначе просто не умеет (в C++ есть передача по ссылке через &, но пока не погружайтесь в эти дебри, мозг совсем взорвется). В функции test присваиваете новое значение параметру array - но main об этом ничего не знает, и существующая в main локальная переменная никак не изменяется. В Си нет аналога var параметров из Паскаля.

Что сделал ответивший вам комментатор? Взял локальную переменную типа "указатель на указатель" и передал внутрь test ее адрес, т.е. передал значение "указатель на указатель на указатель" (проще говоря, передал указатель на array). Далее внутри test изменил содержимое по указателю (т.е. присвоил значение "указатель на указатель"). В результате значение array поменялось.

И еще у вас здесь надо освобождать выделенную память, вызывая free. Все, что выделили через malloc - надо затем освободить, не полагаясь на помощь операционной системы. Каждый вызов malloc должен сочетаться с парным ему free.