How to move objects to new Render Layer?
The way this works is indeed quite confusing.

TL;DR: M moves objects between layers, which are independent of the many layer visibility settings.



Long answer:

There are 20 layers and several independent places where they can be visible or hidden:

Scene layer visibility



These are the layers which are visible in all 3D views with Lock Camera and Layers enabled in 3D view > Header:



Changing the visible layers in any 3D view will change the scene layer visibility and thereby change the layer visibility of any other 3D views with Lock Camera and Layers enabled.



Note that despite being in the renderlayers panel, this setting is global per scene and not unique between renderlayers.

Viewport layer visibility



These are the layers visible in that particular 3D view. If Lock Camera and Layers is disabled, this can be set independently of the scene layer visibility.



Render layers



Unlike layers, of which there are always 20, you can have an arbitrary number of renderlayers.

A Renderlayer contains a layer visibility selection which specifies which layers are visible in that particular renderlayer:



Note that only objects in the active 3D view's visible layers will be rendered. In case of multiple 3D views, the active 3D view is the one under the mouse cursor.

This means that the behavior of the final render can depend on mouse position.

This also means that if all your 3D views have Lock Camera and Layers disabled, the Scene layer visibility doesn't do anything.

This wasn't always the case. In 2.69 scene layer visibility was used instead of viewport layer visibility, which IMO makes a lot more sense..