Here's something I tried that may help you:

First I set the custom polygon display to show hard and soft edges (display/custom polygon display....). This makes the hard edges show up as solid lines and the soft edges show up as dotted lines.

1. I created a cube like you had in the example using the settings shown in the pic below. As you can see the edges of the cube are all hard but the ones crossing through the middle of each full face are soft.

2. With the whole cube selected I made all the normals hard (edit polygons/normals/soften/harden.....). This made every edge hard.

3. I then marquee selected the top faces and selected the default smooth options (twice). As you can see, the top was nice and smooth but the bottom 1/2 of the cube has had the edges softened as well when they started off hard. This has also caused the darkening of the cube as you showed in your example.

4. I then marquee selected the edges of the bottom 1/2 of the cube and hardened the edges again. This got rid of the darkening and made the edges of the bottom 1/2 all nice and crisp again.

The little render at the bottom should show what has happened as well.

Hope this helps you...........