Oh nevermind, just read back and saw that. Guess it pays off to read, doesn't it????! I am not using an "app". I am running standard Linux command-line tools via adb.
After changing the MAC address, the new address is reflected by ifconfig… but I can no longer connect to any wireless network.
It looks like you know what you're doing with the commands, but before what I would always do when spoofing my MAC was separate the commands for changing the MAC and bringing the interface up again into 2 separate commands. I'd say try that to see if it works, but I doubt it will make a difference.
Not sure if it matters but what kernel are you running?