I am wondering - can an Ethereum contract be updated without having to be re-submitted? Say, if I find a bug in my contract, can I fix it without having to create a new contract and making my potential users have to update their references? As I understand, I can always upload a new contract and make that contract fetch the old data plus possibly invalidate the old contract, but that still doesn't let me redirect anyone using the old contract into the new one.
You can separate concerns - have a contract that the users interface with and that has a reference (an address) of another contract that contains the actual logic. Then, you can control the interface contract and update it with the address of the logic contract on updates.
No you cannot. A nice way to mimic mutability is via name registration. You can register a name which you distribute to users or use in dapps and other contracts. Whenever you update you update your entry to point to your current contract address.