diff --git a/PIL/GifImagePlugin.py b/PIL/GifImagePlugin.py
--- a/PIL/GifImagePlugin.py
+++ b/PIL/GifImagePlugin.py
@@ -237,7 +237,10 @@ def _save(im, fp, filename):
         # convert on the fly (EXPERIMENTAL -- I'm not sure PIL
         # should automatically convert images on save...)
         if Image.getmodebase(im.mode) == "RGB":
-            imOut = im.convert("P")
+            palette_size = 256
+            if im.palette:
+                palette_size = len(im.palette.getdata()[1]) // 3
+            imOut = im.convert("P", palette=1, colors=palette_size)
             rawmode = "P"
         else:
             imOut = im.convert("L")
@@ -248,9 +251,13 @@ def _save(im, fp, filename):
         palette = im.encoderinfo["palette"]
     except KeyError:
         palette = None
-        if im.palette:
-            # use existing if possible
-            palette = im.palette.getdata()[1]
+        im.encoderinfo["optimize"] = im.encoderinfo.get("optimize", True)
+        if im.encoderinfo["optimize"]:
+            # When the mode is L, and we optimize, we end up with
+            # im.mode == P and rawmode = L, which fails.
+            # If we're optimizing the palette, we're going to be
+            # in a rawmode of P anyway. 
+            rawmode = 'P'
 
     header, usedPaletteColors = getheader(imOut, palette, im.encoderinfo)
     for s in header:
@@ -391,6 +398,9 @@ def getheader(im, palette=None, info=None):
             for i in range(len(imageBytes)):
                 imageBytes[i] = newPositions[imageBytes[i]]
             im.frombytes(bytes(imageBytes))
+            newPaletteBytes = paletteBytes + (768 - len(paletteBytes)) * b'\x00'
+            im.putpalette(newPaletteBytes) 
+            im.palette = ImagePalette.ImagePalette("RGB", palette = paletteBytes, size = len(paletteBytes))
 
     if not paletteBytes:
         paletteBytes = sourcePalette
diff --git a/PIL/Image.py b/PIL/Image.py
--- a/PIL/Image.py
+++ b/PIL/Image.py
@@ -734,7 +734,10 @@ def convert(self, mode=None, matrix=None, dither=None,
 
         if mode == "P" and palette == ADAPTIVE:
             im = self.im.quantize(colors)
-            return self._new(im)
+            new = self._new(im)
+            from PIL import ImagePalette
+            new.palette = ImagePalette.raw("RGB", new.im.getpalette("RGB"))
+            return new
 
         # colorspace conversion
         if dither is None:
diff --git a/PIL/ImagePalette.py b/PIL/ImagePalette.py
--- a/PIL/ImagePalette.py
+++ b/PIL/ImagePalette.py
@@ -23,13 +23,14 @@
 class ImagePalette:
     "Color palette for palette mapped images"
 
-    def __init__(self, mode = "RGB", palette = None):
+    def __init__(self, mode = "RGB", palette = None, size = 0):
         self.mode = mode
         self.rawmode = None # if set, palette contains raw data
         self.palette = palette or list(range(256))*len(self.mode)
         self.colors = {}
         self.dirty = None
-        if len(self.mode)*256 != len(self.palette):
+        if ((size == 0 and len(self.mode)*256 != len(self.palette)) or 
+                (size != 0 and size != len(self.palette))):
             raise ValueError("wrong palette size")
 
     def getdata(self):
diff --git a/PIL/PngImagePlugin.py b/PIL/PngImagePlugin.py
--- a/PIL/PngImagePlugin.py
+++ b/PIL/PngImagePlugin.py
@@ -505,7 +505,7 @@ def _save(im, fp, filename, chunk=putchunk, check=0):
         else:
             # check palette contents
             if im.palette:
-                colors = len(im.palette.getdata()[1])//3
+                colors = max(min(len(im.palette.getdata()[1])//3, 256), 2)
             else:
                 colors = 256
 

diff --git a/Tests/images/test.colors.gif b/Tests/images/test.colors.gif
new file mode 100644
Binary files /dev/null and b/Tests/images/test.colors.gif differ
diff --git a/Tests/test_file_gif.py b/Tests/test_file_gif.py
--- a/Tests/test_file_gif.py
+++ b/Tests/test_file_gif.py
@@ -38,7 +38,7 @@ def test_roundtrip():
 
 def test_roundtrip2():
     #see https://github.com/python-imaging/Pillow/issues/403
-    out = 'temp.gif'#tempfile('temp.gif')
+    out = tempfile('temp.gif')
     im = Image.open('Images/lena.gif')
     im2 = im.copy()
     im2.save(out)
@@ -46,3 +46,42 @@ def test_roundtrip2():
 
     assert_image_similar(reread.convert('RGB'), lena(), 50)
 
+
+def test_palette_handling():
+    # see https://github.com/python-imaging/Pillow/issues/513
+
+    im = Image.open('Images/lena.gif')
+    im = im.convert('RGB')
+    
+    im = im.resize((100,100), Image.ANTIALIAS)
+    im2 = im.convert('P', palette=Image.ADAPTIVE, colors=256)
+
+    f = tempfile('temp.gif')
+    im2.save(f, optimize=True)
+
+    reloaded = Image.open(f)
+    
+    assert_image_similar(im, reloaded.convert('RGB'), 10)
+    
+def test_palette_434():
+    # see https://github.com/python-imaging/Pillow/issues/434
+
+    def roundtrip(im, *args, **kwargs):
+        out = tempfile('temp.gif')
+        im.save(out, *args, **kwargs)
+        reloaded = Image.open(out)
+
+        return [im, reloaded]
+
+    orig = "Tests/images/test.colors.gif"
+    im = Image.open(orig)
+
+    assert_image_equal(*roundtrip(im))
+    assert_image_equal(*roundtrip(im, optimize=True))
+    
+    im = im.convert("RGB")
+    # check automatic P conversion
+    reloaded = roundtrip(im)[1].convert('RGB')
+    assert_image_equal(im, reloaded)
+
+    

Converting P->RGB, modifying, and converting back to P results in incorrect palette
Running this script (which converts a paletted image to RGB, resizes it with antialiasing enabled, and converts it back to paletted) on the provided in.gif results in an image with a broken palette.

From git bisect, the offending commit is https://github.com/python-imaging/Pillow/commit/06301c9eba3904acf8a9b7b707caa71ba7b6a0d3 - this suggests that it's holding on to the image's original palette, which is no longer valid after the RGB data is modified by the resize operation. (The bug is avoided if you save and reopen the image while it is in RGB mode, immediately before or after the image.resize line.)

```
from PIL import Image

image = Image.open('in.gif')
image = image.convert('RGB')
image = image.resize((200, 150), Image.ANTIALIAS)
image = image.convert('P', palette=Image.ADAPTIVE, colors=256)
image.save('out.png')
```

in.gif:
![in](https://f.cloud.github.com/assets/85097/2058925/55562ea0-8b8d-11e3-8d85-eda144316a85.gif)

out.png with Pillow 2.2.2:
![out-pillow 2 2 2](https://f.cloud.github.com/assets/85097/2058928/6bccd58a-8b8d-11e3-80f2-bc92e5333e85.png)

out.png with Pillow 2.3.0:
![out-pillow 2 3 0](https://f.cloud.github.com/assets/85097/2058929/77151cea-8b8d-11e3-90b4-4c0c69cda085.png)

Converting P->RGB, modifying, and converting back to P results in incorrect palette
Running this script (which converts a paletted image to RGB, resizes it with antialiasing enabled, and converts it back to paletted) on the provided in.gif results in an image with a broken palette.

From git bisect, the offending commit is https://github.com/python-imaging/Pillow/commit/06301c9eba3904acf8a9b7b707caa71ba7b6a0d3 - this suggests that it's holding on to the image's original palette, which is no longer valid after the RGB data is modified by the resize operation. (The bug is avoided if you save and reopen the image while it is in RGB mode, immediately before or after the image.resize line.)

```
from PIL import Image

image = Image.open('in.gif')
image = image.convert('RGB')
image = image.resize((200, 150), Image.ANTIALIAS)
image = image.convert('P', palette=Image.ADAPTIVE, colors=256)
image.save('out.png')
```

in.gif:
![in](https://f.cloud.github.com/assets/85097/2058925/55562ea0-8b8d-11e3-8d85-eda144316a85.gif)

out.png with Pillow 2.2.2:
![out-pillow 2 2 2](https://f.cloud.github.com/assets/85097/2058928/6bccd58a-8b8d-11e3-80f2-bc92e5333e85.png)

out.png with Pillow 2.3.0:
![out-pillow 2 3 0](https://f.cloud.github.com/assets/85097/2058929/77151cea-8b8d-11e3-90b4-4c0c69cda085.png)

