Using a bezier curve, I created the line labeled "A" in the first diagram. I then added a "circle" curve and used "A" as a bevel curve. I ended up with the large UFO looking disc "B". It also looks like Saturn. Note it is a curve and not a mesh yet. I would like to slice a cube using the shape "B". I want to end up with two separate meshes for each half of the cube. The boolean tools are not working. The "slice" command fails because it cannot be applied on curves. I tried converting the "Saturn" looking curve "B" into a mesh and then trying again but I end up with an intact cube. Any idea how this can be accomplished?
I think the best way to achieve what you want will be to use the boolean modifier actually. There are just a few settings we will have to change and a couple extra steps to do.
Let's start with the shape. For this to work, you will need your shape to be a mesh. You can convert your curve to a mesh using the shortcut Alt+C. Now, just to be safe, select everything and remove doubles with W. In my case there were 8 doubles.
Here's the shape I'm using in edit mode. Something to keep in mind is fewer faces is better. Mine is actually a bit too high res really and if you have too many faces it could cause problems. In areas where there is very little change in the curve of the surface you may want to remove some edge loops.
Now we can place this mesh where you want to cut the cube. Make sure that the object completely intersects the cube. If you scale anything in object mode, make sure you apply the scale before proceeding.
Once you have everything set up, duplicate the cube. You can hide one of the cubes, we'll just need it later. Add a boolean modifier to the remaining cube, and set the Operation to Difference. At this point, if you go into wireframe view, it should look pretty good (by pretty good I mean it should look like a wireframe cube intersected by a wireframe version of your original object). If it looks good, apply the modifier. In one of my tests, changing the solver to Carve helped. This will remove one half, but we'll have to do that anyways.
Here's the cube with the Boolean Modifier before it was applied.
If you used Carve, you will have one half left, if not, delete the top or bottom four vertices from the cube so you have just a half left.
Half the shape after applying the modifier and deleting the top 4 vertices. Some nasty shading issues around the edges, but we'll deal with those later.
Now we need to make the other half, so select faces of the cube that will need to be duplicated and duplicate them and then separate them to a new object with P. Now we can unhide the second cube as well.
Faces being duplicated.
Select the new object (which should only be the faces where the two objects will meet) and select the four corner vertices. Set the snapping to face and extrude these vertices along the appropriate axis. Hold Ctrl and hover your mouse over the face of the second cube that these vertices will need to match up to (were just recreating the cube shape here for the second half). The vertices should snap to the corners of the cube. Click to confirm, and create a face with F. Now you just have to fill in the 4 sides on the new object and you're done.
Snapping the corners
Go ahead and delete or move the second cube and the original shape as they are no longer necessary. If you notice any shading issues an edge split modifier on each object will sharpen up the edges nicely (I used this in my file).
Final result are these two shapes which fit perfectly together. If you compare the third image to this one you can see the effect of the edge split on the shading.