Is SpiderOak truly “zero-knowledge”?
Disclaimer: I have never tried using spider oak so I'm only by going what they claim they do, what they told you they do and what the end result looks like.
Given that they claim to be storing your data encrypted and never being able to access it, I would assume the only thing they ever have access to is really the encrypted version of your data. This would mean the application on the client performs all the encryption/decryption operations and only stores the resulting data (and possibly extra encrypted metadata on the server).
This data must be encrypted by something. Now going by their response to you, I would assume they have some hierarchy of keys. My guess would be at least 2 levels, but for simplicity let's just assume one.
This would mean the data is encrypted by some randomly generated key K1 (on your machine). This key is then encrypted by a key K2=PBKDF(32 byte salt,password,16384 rounds). By the preceding ugly description I mean they use the PBKDF2 (Password Based Key Derivation Function v2.) algorithm (using SHA-2) to generate an encryption key from your password. This key K2 would never be stored anywhere (except client memory). It would always be generated on the fly when you want to access your data.
The package that would then be sent to and stored on the Spider Oak servers would be EK1(data),EK2(K1). When you then want to retrieve the data you get the data sent over to you encrypted, and the key sent over to you also encrypted. When you enter your password, PBKDF2 is used to generate K2 which is used to decrypt K1, which is then used to decrypt your data.
So what happens when you change your password? Well the server sends your client all the packages EK2(K1)$ for any K1's it has for your data. Locally these get decrypted by the key generated from the old password, and reencrypted by the key generated from the new password, which gives a new K'2.
When you then come to a different device, fire up your client and try to retrieve your data, the encrypted data come accompanied by the key encrypted using you new password. You enter the password, PBKDF2 does it's magic, and voila you decrypt K1 and then decrypt your data.
edit: GAH how do I get TeX to work here in my posts?
Edit2.: Rereading the information you got from the representative it actually seems like all new K1's are also generated. This seems somewhat fishy in the sense that either they do encryption/decryption on their servers (thus it's not fully zero-knowledge) or they send all the data back to you when you change your password and your client reencrypts it. The first of these seems more likely to be honest, since the overhead for the client otherwise would be quite large. Ofcourse it's also possible the representative doesn't really know what he's saying. I've had that happen multiple times.