unexpected reactions in a quiet simple rigidbody physics simulation
I had no problems with the following settings:


Split Impulse enabled in Scene > Rigid body world:


Both the cube and the sphere with Mesh collision shape and Margin set to 0. 



It is important in this case to set the Margin to 0 because the collision margin for mesh is not embedded into the object, so it will collide with objects that are near the object's surface but not actually touching it (unless it's set to 0).

It is also important to use the Mesh collision shape in this case, because Convex hull will collide with any objects in a convex part of the mesh. 

To visualize this, have a look at the convex hull operator. Try applying it on a Suzanne, the result is roughly what Suzanne's collision shape would be if it was set to convex hull:



Applied to your cube object, you can see why it was causing a collision with the sphere:



Mesh is currently the only collision shape that can handle collisions with concave shapes. There was another shape developed in GSoC 2013 which also could handle concave shapes by breaking them into smaller convex shapes, however this is not yet integrated with blender officially.

The reason why Mesh is necessary for the sphere is because the sphere you are using is not a perfect sphere, while the collision shape is. 

Since the concave depression in the cube exactly matches the "facets" of the UV sphere and the Sphere collision shape's radius is equal to the longest dimension of the object's bounding box, the sphere collision shape will intersect the cube slightly and cause a collision.

To visualize this, I have added a highly subdivided sphere to simulate the perfect sphere of the collision shape and scaled it so that it's radius is equal to the dimension of the UV sphere. I then used Clipping border to make only a tiny cross section visible:



As you can see, the "perfect sphere" intersects the cube, causing a collision to be detected:


The ground cube set to Box collision shape with a .04 margin (the margin is embedded for the box collision shape).
All objects have scale applied (CtrlA) and origins centered (ShiftCtrlAltC).


Result: 



Example blendfile