Скорее всего, проблема в том, что код выполняется дольше, чем заданный интервал. Попробуйте использовать функцию, вызывающую себя рекурсивно через setTimeout.
Здесь в самом конце об этом написано.
Upd. Попробую поподробнее. Только учтите, что я не какой-то опытный гуру, просто на досуге изучаю понемногу.
Из-за того, что код выполняется долго, setInterval помещает в очередь следующий вызов функции до того, как будет вызван clearInterval. Виновато, по-видимому, генерирование псевдослучайного числа — это довольно «тяжелая» операция. В исправленном коде в ответе выше проверка, вызывающая clearInterval вынесена в начало, поэтому проблема не возникла, но всё равно это идеологически неправильно. Не говоря уже о том, что для генерирования случайной перестановки используется вопиюще неэффективный алгоритм, ну это ладно.
Тут рекурсивный setTimeout описан по-русски (немного по-другому код написан, но суть та же), но вообще лучше прочитать
всё целиком, особенно задачи в конце. И вообще, это отличный учебник, рекомендую.