I cloned my Texas linode to my California linode, Cali doesn't work any more

Yup.

Were you using static networking, and if so, did you remember to log in via LISH and update your static networking configuration for your Fremont IP address?

My Auto-configure Networking is set to Yes. Does it matter if one server is Xen while the other is KVM?

Yeah, it was due to the Texas server being Xen and the California server being KVM. After I changed the clone to KVM it works fine. Thanks.