Wat xAnthea zegt klopt inderdaad.
Een GIF bestaat eigenlijk uit heel veel frames achter elkaar. Hoeveel KB je GIF is, hangt af van (a) de lengte van de GIF, dus hoeveel frames het heeft, en (b) de grootte van de frames. De grootte van de frames is nu door de Bokt verkleiner al verkleind, maar je zal er ook nog een aantal frames uit moeten halen om niet over de grens van het maximale aantal KB's te gaan.
Ik doe het altijd met Image Ready, zat bij Photoshop toen ik dat kocht. Je zou even moeten zoeken of er meer (gratis) programma's zijn waarmee je frames kan verwijderen/bewerken.