Similar problem -- I upgraded my MacBook Pro 17" from Tiger to Leopard (10.5.5), and now can't change the ethernet MAC address. This is essential, since I often find myself staying in places where the broadband modem has been 'locked' to a single MAC address.
Following a fair bit of searching in various support fora, I tried various bits of command line geekery, and the shareware ChangeMac utility, all to no avail. Mac address remains stubbornly the same. This is seriously hampering my ability to work on the road, the whole point of carrying the MacBook Pro around! Anyone cracked this yet?!
(I read a rumour this might have been deliberately blocked to (a) prevent people from breaking their Time Machine settings and (b) stop people from spoofing for illegal purposes... if so, I'm deeply unimpressed... I really hope that's just a vicious rumour, and this is an unintended consequence of something else that will shortly be fixed...)