In KDE 3 the bluetooth icon would start up in my systemtray when I log back on. Now in KDE4 I have to keep starting it manually. I leave it running when I log off and it wont come back on automatically after logging back on.

If you are still experiencing this issue, you could try adding a script to ~/.kde4/Autostart that executes kdebluetooth for you. Note that for Intrepid users: replace ~/.kde4 with ~/.kde