It's possible to make animated GIFs that use more than 256 colors per frame (although they'll probably be bigger than a format designed for that sort of thing).
However, due to historical reasons (GIFs optimized for old browsers on slow computers), modern browsers sometimes insert a small delay between image descriptors even if they're in the same frame. I generally consider this a bug. However, there are many broken GIFs out there...