what about:

img = Image.open(GIF_FILENAME)
rgbimg = Image.new("RGBA", img.size)
rgbimg.paste(img)
rgbimg.save('foo.jpg')

[EDIT]

created a test:

from PIL import Image
from collections import defaultdict
import pprint

img = Image.open("kEwfFs3.png")
rgbimg = Image.new("RGBA", img.size)
rgbimg.paste(img)

found_colors = defaultdict(int)
for x in range(0, rgbimg.size[0]):
    for y in range(0, rgbimg.size[1]):
        pix_val = rgbimg.getpixel((x, y))
        found_colors[pix_val] += 1 
pprint.pprint(dict(found_colors))

rgbimg.save('kEwfFs3.jpg')

And that outputs:

{(0, 0, 0, 255): 747802,
 (1, 1, 1, 255): 397,
 (2, 2, 2, 255): 299,
 (3, 3, 3, 255): 255,
 (4, 4, 4, 255): 221,
 (5, 5, 5, 255): 200,
 (6, 6, 6, 255): 187,
 (7, 7, 7, 255): 138,
 (8, 8, 8, 255): 160,
 (9, 9, 9, 255): 152,
 (10, 10, 10, 255): 122,
 (11, 11, 11, 255): 116,
 (12, 12, 12, 255): 144,
 (13, 13, 13, 255): 117,
 (14, 14, 14, 255): 117,
 (15, 15, 15, 255): 102,
 (16, 16, 16, 255): 119,
 (17, 17, 17, 255): 299641,
 (18, 18, 18, 255): 273,
 (19, 19, 19, 255): 233,
.................... etc .......
.................... etc .......
 (249, 249, 249, 255): 616,
 (250, 250, 250, 255): 656,
 (251, 251, 251, 255): 862,
 (252, 252, 252, 255): 1109,
 (253, 253, 253, 255): 1648,
 (254, 254, 254, 255): 2964175}

Which is what you would expect. Is your output different?

How about doing it with Pillow:

from PIL import Image
img = Image.open('image.png').convert('L')
img.save('greyscale.png')

If an alpha (transparency) channel is present in the input image and should be preserved, use mode LA:

img = Image.open('image.png').convert('LA')

Using matplotlib and the formula

Y' = 0.2989 R + 0.5870 G + 0.1140 B 

you could do:

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.image as mpimg

def rgb2gray(rgb):
    return np.dot(rgb[...,:3], [0.2989, 0.5870, 0.1140])

img = mpimg.imread('image.png')     
gray = rgb2gray(img)    
plt.imshow(gray, cmap=plt.get_cmap('gray'), vmin=0, vmax=1)
plt.show()