Обратил внимание, что модуль re не может нормально работать со строками, которые представлены списками символов (которые, например, получаются, если просто в консоли закавычить русские буквы) и прекрасно работает со списками utf8-байт.
Т.е. для одного и того же регекспа (он содержит только латиницу) получаю:

17> re:run("abcd", Re).
nomatch
18> re:run("абвг", Re).
** exception error: bad argument
     in function  re:run/2
        called as re:run([1072,1073,1074,1075],
                         {re_pattern,1,0,
                                     <<69,82,67,80,97,0,0,0,0,2,0,0,7,0,0,0,
                                       1,0,0,0,34,0,34,...>>})

Т.е., получается, для внутреннего представления строк стоит юзать utf-8 бинари, либо списки utf8-байт?

Если имеет значение:

Erlang R13B (erts-5.7.1) [source] [64-bit] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]