Matrix parameters work fine as input, but if I change the output to just a sequence of longs, then I get the #NAME error again (and I remembered to updated the Python return value to (1,2) ).
Another possibility could be to interface my Python program from C, which is moderately easy: http://abel.ee.ucla.edu/cvxopt/examples/miscellaneous/embed_cvxopt.c/view (and I guess that C++ is not much harder), but I doubt than many Spreadsheet optimization users would bother (or know how) to compile their own add-ins.