(In reply to comment #17)
> Make sure you have the updated RLC ucode in addition to the UVD ucode. 
> Unfortunately, I can't reproduce this on the UEFI systems I have access to.

Benjamin and Parag have already indicated which firmware versions they are
using, and I feel it's safe to assume that Christian is also using the proper
versions as well.

I see that I have forgotten to list my versions:  the *_rlc.bin (and *_uvd.bin)
files I use were listed in comment 9, and all 4 of them are dated Apr. 2, 2013.
 They were obtained from

    http://people.freedesktop.org/~agd5f/radeon_ucode

on Apr. 28.