Okay I really didn't want to have to format my OS, it's like the fifth time now!
My OS: Ubuntu 14
Anyways, I've deployed dozens of Ethereum contracts without problem. Then, after updatting to newest Ethereum I've been unable to deploy anything since. This is what happens:
No matter how much ether I send, or slide the bar up and down, nothing changes the provided fee being less than what is required.
I would try "hacking" Mist by editing the source code to manually change values, but so far I haven't been able to do that.
No problem creating wallets by the way.. Except it says it will consume 0 gas (I don't believe it did that before) Any ideas what I should do? I'll accept "format" as an answer