You asked for intuitive sense and I'll try to provide it. The formula is:
$$\Delta S = \frac{\Delta Q}{T}$$
So, you can have $\Delta S_1=\frac{\Delta Q}{T_{lower}}$ and $\Delta S_2=\frac{\Delta Q}{T_{higher}}$
Assume the $\Delta Q$ is the same in each case. The denominator controls the "largeness" of the $\Delta S$.
Therefore, $\Delta S_1 > \Delta S_2$
In each case, let's say you had X number of hydrogen atoms in each container. The only difference was the temperature of the atoms. The lower temperature group is at a less frenzied state than the higher temperature group. If you increase the "frenziedness" of each group by the same amount, the less frenzied group will notice the difference more easily than the more frenzied group.
Turning a calm crowd into a riot will be much more noticeable than turning a riot into a more frenzied riot. Try to think of the change in entropy as the noticeably of changes in riotous behavior.
Let's start with the physical interpretation. We are considering an ideal gas of particles in equilibrium at some temperature $T$. Let's ask the following question: if the system is in equilibrium, why don't all particles have the same speed? Answer: because the particles interact through collisions. Imagine that one could prepare a system in such a way that each particle of an ideal gas enters a box with a set speed $v_0$. Will all the particles maintain the same speed $v_0$ once the collisions start to occur? No. If the particles never collided, they would maintain their initial speed - but the particles do collide. We know from simple mechanics that collisions lead to a whole range of speeds in different directions, depending on the angle of incidence etc.
Instead of having a set speed $v_0$ then we will have a whole set of speeds. Some of those speeds will be more probable than others. For example, it takes a very special collision for a particle to transfer all its kinetic energy to the other particle, thus resulting in the initial particle having speed zero after the collision. There is a largely wider family of collisions in which the particle's speed diminishes by some percent, but is nonzero. Overall, we can say that there are some fluctuations of the speed values around some most probable value (which may have something to do with $v_0$). Now here comes the important point: just how big these fluctuations are depends on the temperature. For small temperatures fluctuations are subtle, and for larger temperatures the fluctuations are large. You can think that for larger temperatures (and correspondingly larger average speeds) there is a larger number of speeds accessible with some significant probability. This is mirrored in the behavior of the Maxwell-Boltzmann distribution function (after all this is why we choose this distribution function in the first place: because it describes the real world!).
Now on to math. We consider the Maxwell-Boltzmann distribution function,
\begin{eqnarray}
f(v) = \sqrt{\left(\frac{m}{2 \pi k_BT}\right)^3} 4\pi v^2 e^{- \frac{mv^2}{2k_BT}}~,
\end{eqnarray}
where $m$ is the mass of the particle, $v$ is its speed, $T$ is the temperature of the system and $k_B$ is the Boltzmann constant. Let us see that the dimension of the distribution function is
\begin{eqnarray}
\big[f(v) \big] = \sqrt{\left(\frac{\textrm{kg}}{\frac{\textrm{J}}{\textrm{K}} \times \textrm{K}} \right)^3} \frac{\textrm{m}^2}{\textrm{s}^2} =\left[\frac{1}{v}\right]~.
\end{eqnarray}
This agrees with our interpretation of $f(v)$ as probability per unit interval of speed. After integrating over speed we will get a dimensionless quantity: probability. All units agree.
Let us now see how the distribution function behaves for different values of $T$. First, let us find: where is the peak of the distribution function? This peak will correspond to the value of $v$ that is most probable. We can easily calculate that with
\begin{eqnarray}
&& \frac{d}{dv} f(v) = \sqrt{\left(\frac{m}{2 \pi k_BT}\right)^3} 4\pi \left(2v e^{- \frac{mv^2}{2k_BT}} + v^2 \left(-\frac{2mv}{2k_BT} \right)e^{- \frac{mv^2}{2k_BT}} \right)= 0 ~~~\Rightarrow \\
&& \Rightarrow ~~~v_{\textrm{peak}} = \pm \sqrt{\frac{2k_B T}{m}} ~.
\end{eqnarray}
Clearly, the peak of the distribution function takes place when the argument of the exponent is equal $-1$. Note that for small $T$ the peak will take place at some small velocity, while for large $T$ the peak will take place at some larger velocity. The value of the distribution function at the peak is
\begin{eqnarray}
f(v_{\textrm{peak}}) = \frac{1}{e} \sqrt{\left(\frac{m}{2 \pi k_BT}\right)^3} 4\pi \frac{2k_B T}{m} = \frac{1}{e} \sqrt{\frac{8m}{ \pi k_BT}} ~.
\end{eqnarray}
We can see that for small $T$, $f(v_{\textrm{peak}})$ is going to be large because $T$ is in the denominator, and for the same reason $f(v_{\textrm{peak}})$ will be smaller for bigger $T$.
We can now make some comparisons. For example, we can calculate for what ranges of $v$ the value of the distribution function is more than $\frac{1}{e}f(v_{\textrm{peak}})$ (i.e., what values of $v$ land us at the "top of the hill" of the distribution function). This is not hard to calculate: we set a condition
\begin{eqnarray}
&& f(v) = \frac{1}{e}f(v_{\textrm{peak}}) ~~~\Rightarrow ~~~ v^2 e^{- \frac{mv^2}{2k_BT}} = \frac{1}{e^2} v_{\textrm{peak}}^2 ~.
\end{eqnarray}
In order to solve this equation let us go to the first order approximation,
\begin{eqnarray}
e^{- \frac{mv^2}{2k_BT}} \approx 1 - \frac{mv^2}{2k_BT}~.
\end{eqnarray}
Then we want to solve
\begin{eqnarray}
v^2 \left(1 - \frac{mv^2}{2k_BT} \right) = \frac{1}{e^2} v_{\textrm{peak}}^2~,
\end{eqnarray}
which is just a quadratic equation in $v^2$ leading to
\begin{eqnarray}
v^2 = \frac{k_BT}{m} \pm \frac{\sqrt{e^2 - 4}}{e}\frac{k_B T}{m}
\end{eqnarray}
Since
\begin{eqnarray}
\sqrt{1 - \frac{4}{e^2}} \approx 0.677 \approx \frac{1}{2}
\end{eqnarray}
(we just want to assess the overall nature of the function, so such approximations are valid), we can write
\begin{eqnarray}
v^2 = \frac{k_BT}{m} \pm \frac{1}{2}\frac{k_B T}{m} = \frac{1}{2}\frac{2k_BT}{m} \pm \frac{1}{4}\frac{2k_B T}{m} = \frac{1}{2}v^2_{\textrm{peak}} \pm \frac{1}{4}v^2_{\textrm{peak}}~.
\end{eqnarray}
Therefore for the value of the distribution function to be smaller than the peak value by no more than $e$, the velocity has to lie within
\begin{eqnarray}
v^2 \in \left(\frac{1}{4}v^2_{\textrm{peak}}, \frac{3}{4}v^2_{\textrm{peak}} \right) = \left(\frac{k_B T}{2m}, \frac{3k_B T}{2m} \right)~.
\end{eqnarray}
Note that this range depends on the temperature $T$! For small temperatures the range is smaller, while for large temperatures the range is larger. This means that the slope for the larger temperatures must be less steep if the value of the distribution function must decrease by a constant factor of $e$ over a larger range of velocities.
The mathematical behavior of the distribution function thus agrees with our qualitative understanding!
Best Answer
It's hard to say anything concrete without knowing exactly what material your band is made of, but I can at least propose one option. Rubber bands (and other polymers, etc) pass through a "glass transition" at a temperature below their melting point. As the material passes through this temperature (with temperature increasing) it transitions from a hard, brittle state to compliant state. In polymers, this is because at the glass transition temperature $T_g$, the free energy is sufficiently high to allow the molecular chains to slide past one another when force is applied. The transition is reversible, so the material will re-enter the brittle state at lower temperatures.
Now, rubber bands are typically made of natural rubber (polyisoprene), which has a glass transition temperature of -70C, but it's possible that the one you're using may have been made of a different material with a higher $T_g$. It's worth noting that the glass transition occurs over a fairly wide range of temperatures, so you may still be observing the tail of its effects even if you're still far from the "official" value for your material.
Half-baked molecular explanation: You're correct with your reasoning about the effects of entropy. At temperatures far greater than the glass transition (but still below melting), the rubber band will actually stiffen due to the entropic origins of its elasticity. However, the glass transition is a particularly obvious example of "kinetics vs thermodynamics" in nature. The brittle state is simply due to lack of energy to overcome the activation energy of polymer chains moving past one another. The equilibrium state is dictated by the entropic elasticity, but it can never get there on an observable time scale.
More Information: https://en.wikipedia.org/wiki/Glass_transition