Completely reinstalled the cluster with completely new config. This time on dedicated hardware (6-core, 32GB servers). Exactly the same happens; as soon as some queries are executed the server on which those queries were excuted crashes. We're beginning to feel a bit hopeless about this. This MUST be our fault but we can't figure out what's happening. And then again - we don't think the crashing is by design either. It would be nice if someone could point us in SOME direction... Bump.

121213 21:12:00 [ERROR] WSREP: FSM: no such a transition REPLICATING -> REPLICATING
20:12:00 UTC - mysqld got signal 6 ;
This could be because you hit a bug. It is also possible that this binary
or one of the libraries it was linked against is corrupt, improperly built,
or misconfigured. This error can also be caused by malfunctioning hardware.
We will try our best to scrape up some info that will hopefully help
diagnose the problem, but since we have already crashed, 
something is definitely wrong and this may fail.
Please help us make Percona Server better by reporting any
bugs at http://bugs.percona.com/

key_buffer_size=33554432
read_buffer_size=131072
max_used_connections=6
max_threads=500
thread_count=6
connection_count=6
It is possible that mysqld could use up to 
key_buffer_size + (read_buffer_size + sort_buffer_size)*max_threads = 1127092 K  bytes of memory
Hope that's ok; if not, decrease some variables in the equation.

Thread pointer: 0x2efacd20
Attempting backtrace. You can use the following information to find out
where mysqld died. If you see no messages after this, something went
terribly wrong...
stack_bottom = 7fba485c7e20 thread_stack 0x40000
mysqld(my_print_stacktrace+0x2e)[0x7cd73e]
mysqld(handle_fatal_signal+0x481)[0x6b1681]
/lib/x86_64-linux-gnu/libpthread.so.0(+0xfcb0)[0x7fba5b47ecb0]
/lib/x86_64-linux-gnu/libc.so.6(gsignal+0x35)[0x7fba5b0e8445]
/lib/x86_64-linux-gnu/libc.so.6(abort+0x17b)[0x7fba5b0ebbab]
/usr/lib/libgalera_smm.so(_ZN6galera3FSMINS_9TrxHandle5StateENS1_10TransitionENS_10EmptyGuardENS_11EmptyActionEE8shift_toES2_+0x180)[0x7fba59bf2070]
/usr/lib/libgalera_smm.so(_ZN6galera13ReplicatorSMM9replicateEPNS_9TrxHandleE+0xc5)[0x7fba59be7fb5]
/usr/lib/libgalera_smm.so(galera_pre_commit+0xb0)[0x7fba59bfa680]
mysqld(_Z22wsrep_run_wsrep_commitP3THDP10handlertonb+0x753)[0x667c63]
mysqld[0x6689fb]
mysqld(_Z15ha_commit_transP3THDb+0x13b)[0x6b42eb]
mysqld(_Z17trans_commit_stmtP3THD+0x25)[0x65d515]
mysqld(_Z21mysql_execute_commandP3THD+0x63c)[0x5ac45c]
mysqld(_Z11mysql_parseP3THDPcjP12Parser_state+0x2d1)[0x5b29f1]
mysqld[0x5b2b62]
mysqld(_Z16dispatch_command19enum_server_commandP3THDPcj+0x16b9)[0x5b4e79]
mysqld(_Z10do_commandP3THD+0x171)[0x5b5521]
mysqld(_Z24do_handle_one_connectionP3THD+0x180)[0x64fcd0]
mysqld(handle_one_connection+0x51)[0x64fe91]
/lib/x86_64-linux-gnu/libpthread.so.0(+0x7e9a)[0x7fba5b476e9a]
/lib/x86_64-linux-gnu/libc.so.6(clone+0x6d)[0x7fba5b1a44bd]

Trying to get some variables.
Some pointers may be invalid and cause the dump to abort.
Query (7fb334004b60): is an invalid pointer
Connection ID (thread ID): 9
Status: NOT_KILLED

You may download the Percona Server operations manual by visiting
http://www.percona.com/software/percona-server/. You may find information
in the manual which will help you identify the cause of the crash.