I suspect that looking at how modules like PIL and Numeric do things in their C code would help

Some argument processing will possibly be better done in Python before calling into the C code.

Verifying the contents of lists of lists seems like overkill, it might be better to call type conversion method from with the C, or even dispense with these checks but make sure that the contents are of the correct type when inserted (e.g. by using your own list wrapper class that does the checking  and/or conversion at insertion).