Trouble Getting KNetworkManger to Start Automatically?

Just do what this guy did:

Check ~/.kde4/share/config/networkmanagementrc and make sure that Autostart=true is listed under the [General] section.

That did it for me. No amount of messing with Autostart in the KDE System Settings helped.