Since no one has responded, I think I will...
I did the download of the 2.6.32.12 kernel again, but I left the boot order in PCC alone (letting it boot the default kernel at /boot/vmlinuz). Before the initial boot of the new kernel, I went 'su' and modified the symbolic entries within /boot so that they (vmlinuz, initrd.img, System.map etc.) ALL pointed to their 2.6.32.12 equivalents and no longer pointing to the .11 versions.
After boot, I ran the Guest Additions again, and rebooted again, and things now seem to be working correctly.
The key to this also, is I did a shutdown and NOT a restart.
Each and every time. Shutdown works, restart does not.
I don't know if it's a VirtualBox issue (I'm running latest production version 3.1.6) or an interaction between Mac OS X 10.6.3 and VirtualBox 3.1.6 and PCLinuxOS 2010 (or some combination).
Has this happened to anyone else?