I tracked down, and I noticed following code was invoked.

Lib/decimal.py (release-maint25 Decimal#_rescale)

1912: if watchexp and digits > context.prec:
1913:     return context._raise_error(InvalidOperation, 'Rescale > prec')

from decimal import *
d = Decimal("23.08589694291355371979265447")
print d % Decimal("2.302585092994045640179914546844") # NaN
print Decimal("0.060046012973097317993509001560")._rescale(-30) # error

Length of decimal seems to be important, so I changed length and it
seemed working.

print d % Decimal("2.302585092994045640179914547") #
0.060046012973097317993509000

Maybe is this intended behavior? Still I feel 2.6's behavior is less
suprising though...