Cool I will do that. But how come blockchain.info recommends way lower fees?
I don't know. Blockchain.info has a lot of problems in general.
Also the service I paid to says that they have received the money but I have to wait for confirmations and it doesn't let me generate a new address to sent Bitcoins at... when I cancel the transaction I guess I will be able to create a new sending address? Or do I send to the same address?
It depends on the service. Since addresses don't expire, you can still send to the same address. It's on the service to know that you attempted to bump the fee. If your transaction confirms but the service isn't recognizing it, then contact their support because that is on their end.
Damn this is insane, looks like its going to take forever rescaning it.. i want to sleep.
It will fix your problem. Rescanning should not take too long, but it does take a while since it has to scan through the entire blockchain.