Solution: Declare the class public. I mean seriously, you missed that?
More surprising than not getting any hits for this message on Bing or Google is not catching the problem myself for the past [insert embarrassing amount of time here]. Serves me right for going manual and ignoring my own project templates. Even better, I hand-coded my own .webpart file so the WP only broke when I added it to the page. My first clue should have been when it didn't appear on the Web Part Gallery's New page (where it's far easier to have the darn XML generated for you).