This is "normal" in the sense that blender is doing it's job correctly for what you're asking it to do. I think the problem lies with how your UVs are set up. Make sure to get set up the UVs so that you don't get very tiny pieces that would lead to lighting errors like that. You can either try to expand the UVs (and bake at a higher resolution with higher settings), or you can just fix the AO bake with photoshop.

For me, I like to render my AO at 4x the final size of the texture and with high settings. Then I scale it down in photoshop and try to paint over any small errors in the bake.

Ok, i'm gonna redo the parts of the UV with errors in it and if that doesnt help, i'll fix them in photoshop. Thanks Helljumper!