You say you made the video?
Did it have square pixels?
I just went back into Premiere and changed the Sequence settings of my video to 4:3 and now it's working. I guess PS can only do 4:3 GIFS...
If there's a way to do 16:9 GIFS, I'd love to know!