The particles are falling on the collision but half of them are upside the collision and half are down the collision plane.
Particles are not objects in blender, they do not have a geometry, even if you attach an object to them, the geometry is not simulated physically with the particle system.
The spheres will always intersect the plane as long as the particle is flush on it.
If you want your particles to be physical, you need the Molecular addon: http://pyroevil.com/category/scripts-addons/molecular-script/
Alternatively you would need to run a physics simulation using rigid bodies.
Or in this case the collision margin of the plane needs to be the -radius- of the red sphere. Note that this will still make the red spheres intersect each other since theres no way to stop that from occurring with the vanilla particle system.