The index into a color table is not a good way to slowly change between two colors, since the index is just a number - it doesn't really relate to the physical properties of the color.

Decide on a start color and an end color as RGB values.

Start: R = 255, G = 0 B = 0.
End: R = 170, G = 90, B = 10.

Decide how many steps to go from first color to second color. There is no use to have many steps if you have very few instensity levels available for each primary color - you are already using PWM so you can't use PWM to interplate between the PWM steps.

Let's say you want 4 steps.

That means:

Step 0: 255 0 0
Step 1: 233 22 2
Step 2: 212 45 5
Step 3: 191 67 7
Step 4: 170 90 10

But you have only 5 levels available for each primary, meaning 0, 64, 128, 192, 255.

So you have to find the alternatives with the least errros.

Step 0: 255 0 0 is a perfect match
Step 1: 233 22 2 -> 255 0 0 (the step was too small compared to available intensities)
Step 2: 212 45 5 -> 192 64 0
Step 3: 191 67 7 -> 192 64 0
Step 4: 170 90 10 -> 192 64 0

As you can see - the interpolation into steps is only meaningful if the start and end colors have a large change in the color channels, in relation to the available number of steps for the primary colors. In my example, the color would jump instantly from a start color with perfect match to an end color with a quite bad match. You really should try to get your PWM solution to support more steps than 5/primary channel. Of course, this means that you can't store a color as an 8-bit value.

Another thing here is that the above is an example of interpolation in RGB space. That is ok if the start and end color only changes one color channel at a time. But when two or all three color channels are changing between start and end color, then the RGB interpolation isn't so beautiful. It interpolates in a color cube. Moving from one strong color to another strong color can then result in intermediate gray colors, or at least colors with very little saturation.

It is then better to convert the start and end colors into a HSV cone shape. Now you can interpolate an angle, allowing you to keep up the saturation while just changing the hue or value. See illustration 2b in:
http://en.wikipedia.org/wiki/HSL_and_HSV