The amount of BTC being sent does not matter. What matters is the actual size of the transaction in bytes. If you send the same amount in two transactions but one has more inputs than the other (thus making it bigger), then it will require a higher fee. Also, the condition of the network is constantly changing, so what worked a month ago may not work now.
It is stuck probably because your fee is too low. According to
https://bitcoinfees.21.co/ (which is known to be fairly accurate)
For the median transaction size of 258 bytes, this results in a fee of 20,640 satoshis (0.13$).
2800 satoshis is not enough.
Since you are using Bitcoin Core, you should just use the fee that Bitcoin Core recommends. If you choose the "Recommended" option and move the slider to "Fast", it will give you a fee that is usually enough to get the transaction confirmed in the next block.
To fix this, in Bitcoin Core, go to Help > Debug Window and then the Console tab. In the box at the bottom, type
abandontransaction
Where is the txid of your stuck transaction (when copying from the transaction list, make sure you remove the -000 that Bitcoin Core appends to the txid). Then hit enter. This will enable you to respend the inputs that you used in your stuck transaction so you can send it again but with a higher fee.
Cool I will do that. But how come blockchain.info recommends way lower fees?
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?