I messed with it a few hours again yesterday, but no luck so far. Anybody else can confirm/deny that they have this problem as well? I guess this is either a bug with NetworkManager or a compatibility issue with the hardware. It would be really nice to let Network Manager handle the connections, but it seems the facility for changing the MAC address is broken.
I'm powered by the e1000e driver. lshw gives me this:
$ lshw -C net
WARNING: you should run this program as super-user.
description: Ethernet interface
product: 82579LM Gigabit Network Connection
vendor: Intel Corporation
physical id: 19
bus info: pci@0000:00:19.0
logical name: eth0
width: 32 bits
capabilities: bus_master cap_list ethernet physical tp 10bt 10bt-fd 100bt 100bt-fd 1000bt-fd autonegotiation
configuration: autonegotiation=on broadcast=yes driver=e1000e driverversion=1.5.1-k firmware=0.13-3 latency=0 multicast=yes port=twisted pair
resources: irq:47 memory:f3500000-f351ffff memory:f353b000-f353bfff ioport:6080(size=32)