...
I paid the fees according to what the wallet advised me, Ive done this hundreds of times.
why all of a sudden is this happening ??
help would be much appreciated as I don't want this to happen again ??
You may already be doing this, but you want to make sure that Bitcoin Core is running for a little while so that it can estimate the fees correctly. E.g., don't just start it and send.