I use the settings below.
Make sure you are in 'Blender Render' engine and NOT in Cycles. Then, change the samples from the standard 5, to 32.
Then, in the bake settings, I use the below.
Click normalise and I usually change the bleed to around 2 pixels (but, that's personal preference and doesn't really have any bearing on this).
This is the result. It will take a little longer to bake, but, the result is worth it. If you feel it's still not smooth enough, you can up the samples. This was baked to a 2048px texture.
Two minor points. If you are blending the AO over the diffuse texture, you can always use the blur tool a little, just to get the result a little smoother. Also, when you are creating your textures, go big. I start all of my textures as 4096px, then, scale them down. You can get more detail into a larger texture sheet. These details will be translated down to the smaller sizes, but, it's hard to get the good details in if you are starting at 512px.
Again, these are just my opinions and my work flow.
Cheers
Jay.