I don't know what the issues you're having are, so I can't be too specific, but I'm assuming you're trying to fix a bug in the perl/XS binding to the library, assuming the C library (and the perl binary!) are working correctly.
My first stab at these kinds of problem is usually to put a bunch of assert() statements in the XS code, compile the module making sure that NDEBUG is undefined, and rerun the test. That should halt the code at any moment the assertions don't hold, and should tell you at least where your assumptions are wrong, and I think it would also give you a break point in GDB, though I must confess I don't really use debuggers at all, except to inspect core dumps.
I'm not a wizard with perl internals or C, but just getting in the code and trying to confirm my expectations works most of the time when dealing with algorithmic mistakes. In my experience, memory allocations etc errors are actually harder to find, which is why I like valgrind so much.