Everything is upgraded to the latest "release" versions and MySQL is set to whatever defaults it comes with.

Just wondering if anyone else has seen this happen.

You can select restart MySQL from the WHM and sometimes it will restart OK but other times it fails to restart and you have to hit restart again for it to go.

Just for fun I tried a complete reboot and then MySQL didn't start at all so I hit the WHM restart and it was up again.

Check /var/log/messages and /var/lib/mysql/hostname.err there is probably some information

Yea, duhhhh... I forgot to look there! Thanks for the reminder. It's:
/var/log/mysqld.log

And it says:
Can't create/write to file '/tmp/ib9uenwA'
InnoDB: Error: unable to create temporary file; errno: 13
Can't init databases
Aborting

No reason it couldn't write that file. Strange...

It works the second time I hit restart though and nothing really changed.

I am just wondering if it's a cPanel bug or a problem with my setup.

No it is a permission problem on your system. You have probably tried to secure your /tmp without doing it correctly. Simply chmod 0777 /tmp. Also the hostname.err file I stated above would have told you the same thing, that is just another location for it

There is no .err file in that location, this is a start up issue.

And if it's a permissions problem then why does it start up the next time I hit restart, or after boot when I hit restart?

And I used cPanel's set up for /tmp and I must say it's a very nice script that does it, has lots of checks for everything.