For now you just have to wait until the SD transaction is mined.
There is a change pending review that would help in situations like this:
https://github.com/bitcoin/bitcoin/pull/2814It would mean you could attach a higher fee to your second transaction and it would encourage mining of the first. But the code isn't merged yet.
Luke-Jr's pull-req is the completed one:
https://github.com/bitcoin/bitcoin/pull/1647 My code is just taking his idea and applying it in a way that is more general and reliable. (Luke's patch is good, it's just you can extend the idea even further with P2P protocol changes so nodes can know how to retrieve parent transactions if required)
Eligius and another pool uses Luke's patch already, so re-spending your stuck transaction with a fee will help. Unfortunately I don't think any Bitcoin wallets have an easy way to do this; it'd be really good if someone writes that code. The user should be able to click on a payment, either to you or from you to someone else, and say "Increase fee" and have the wallet software take the correct steps.