It's not about gambling, it's about how expensive their implementation is. They outsourced the cost and they're not paying (enough) themselves.
They are paying exactly what miners require. If you want them to pay more, then miners have to require more.
The answer was already given.
The proposed transaction fee solution works in most cases, but not SatoshiDice because they have social-engineered gamblers into covering the fees for them, and to make it worse the gamblers are willing to pay a higher fee than real users. If Bitcoin had achieved critical mass already, we might have been able to just say "too bad, deal with higher fees", but at this pre-adoption stage the response to that would almost certainly be "screw you, I'll stick with VISA".
In other words: to ease adoption, bitcoin transactions need to be cheap for users who transfer value, but they need to be expensive for SD which is just abusing the system for information transfer. If we didn't care for bitcoin success, high fees would be the answer.
Why do "normal" users deserve to use the network more cheaply than Satoshi Dice users? They're both using the same resources. But this is more of a point of opinion than anything.
If any individual miner or pool agrees with Luke-Jr, then the solution for them is simple: Set their miners or pools to only accept SD transactions which meet whatever arbitrary criteria they believe is fair. Maybe this is a higher fee, in which case they should notify SD of the change, so that SD can choose whether to pay a higher fee to be included in their blocks. Maybe this is the belief that SD is the scum of the earth, and they will never process SD transactions. That's ok too - it is entirely their decision. The rest of the miners will continue to set other arbitrary rules for what transactions are accepted or denied when they hit a block.