Or you could just wait it out. If you're playing at Medium and don't do anything more to anger them (like marching armies on their territory, or taking their provinces), then relations should sloooowly normalize towards the better on every turn. Keep trying for gift opportunities, but realize you may not be able to do anything in the current turn, or even the next few, until relations normalize a little bit in your favor. Diplomacy does work on the M setting (not on H or VH), but you have to give it time.