I ran into similar issues when developing the Perl 6 metamodel stuff for Pugs, and more recently with Class::MOP. I use the Sub::Name module which has worked great for me, it is also written in XS, you might be able to get a few pointers out of the code (or better yet, just use it, why reinvent the wheel).

Of course I might also be 2 years to late with this comment too :)