Sweeeeet. Found the issue-
The problem is that when the X-server shuts down it overwrites /etc/ati/amdpcsdb (where aticonfig stores many of its settings as well as where amdcccle stores its stuff). Stupid? Yes.
So the trick to making the changes persistent is to only make them when the X-server isn't running.
I was able to sort out underscan by doing the following on the media director (as root):
In that way, the setting above (default underscan off) somehow survives the reboot