Does anyone else have this issue? Is there a remedy for this somehow?
Bitcoin wasn't designed to be good at doing transactions the way it is being used for SatoshiDICE wagering (small amounts and/or spending of coins that were only recently received.)
You might want to find an alternative wagering service that doesn't require a new transaction for each wager. bitZino, who also offers "provably fair" wagering, has a roulette game which accepts 0.01 wagers (or even smaller amounts) and might be a good alternative to a blockchain-based wagering service.