Writing a Storable file from C does not sound like an easy solution to me. Here are alternate ways to solve this problem. I am assuming throughout that there is some C library you have that provides an interface into this data structure. If it doesn't exist yet, you should be able to build one fairly easily.

1. Use a standard data exchange format such as XML or YAML. As you have discovered, this can be slow.
2. Come up with a format for the data and use pack/unpack to pass data between C and Perl (great if it works but it won't always work).
3. Write an XS interface for a C library that has the complete specification for the data structure then access your C library directly from Perl. This is a lot of work but should be very fast.
4. Use swig to generate an interface into your C library. This actually builds an XS interface. I don't hear about people doing this much for Perl, and in my one experience with such an interface we found some performance silliness that we cleaned up, but it may save you some work.
5. Use Inline::C in Perl to access your data. This is simpler to set up than the other versions, is fast (except the first time you call it), but requires a C compiler and some (fairly minimal) C knowledge from your Perl developers.

From your question I suspect that you're using Storable. Be warned that the direct C solutions will not necessarily play well with Storable if your Perl developers are using that. The solution to that is to build STORABLE_freeze and STORABLE_thaw hooks that serialize and deserialize your C data structures into a string that Storable can use.