mdadm fails to assemble RAID5 from 4 LUKS devices on boot

My setup is the following: 4 LUKS encrypted drives with mdadm RAID5 on top. The reason I encrypted first and then added them into the array was based on performance: 4 threads doing encryption/decryption instead of just 1. The max speed of this array vs Raid5 first, encrypt later is 169 MB/s vs 90 MB/s. This setup used to work perfectly in 9.10, but stopped working in 12.04. mdadm always thinks the array is degraded with two disks (usually random) marked as spares. The array is perfectly healthy if I assemble it after the booting process is finished
Yes, I ran this after mdadm.conf update:
sudo mdadm --udev-rules
sudo update-initramfs -u -k 3.2.0-32-generic

cat /etc/mdadm/mdadm.conf
# mdadm.conf
#
# Please refer to mdadm.conf(5) for information about this file.
#
# by default (built-in), scan all partitions (/proc/partitions) and all
# containers for MD superblocks. alternatively, specify devices to scan, using
# wildcards if desired.
DEVICE partitions
# DEVICE /dev/mapper/raid5_1_crypt /dev/mapper/raid5_2_crypt /dev/mapper/raid5_3_crypt /dev/mapper/raid5_4_crypt
ARRAY /dev/md0 uuid=cbb6468c:4dbcc21a:b1397419:998055ac
# ARRAY /dev/md0 level=raid5 num-devices=4 spares=0 devices=/dev/mapper/raid5_1_crypt,/dev/mapper/raid5_2_crypt,/dev/mapper/raid5_3_crypt,/dev/mapper/raid5_4_crypt

# auto-create devices with Debian standard permissions
CREATE owner=root group=disk mode=0660 auto=yes

# automatically tag new arrays as belonging to the local system
HOMEHOST <system>

# instruct the monitoring daemon where to send mail alerts
MAILADDR root

# definitions of existing MD arrays

# This file was auto-generated on Sat, 13 Oct 2012 22:37:39 -0400
# by mkconf $Id$

# POLICY domain=arbitrary_string metadata=0.90 action=include