Cutting heart shape in a mesh
Your specific problem (based on your blend file) is a faulty heart mesh. If you press z to see the wireframe mode and this will become obvious. You need to have a mesh that does not contain inner geometry or walls, or double edges/vertices, which this mesh contains both. Unfortunately the tutorial and method you were following to create the heart is "simple", but rather faulty and bound to get you into trouble in the future.



These mesh issues caused an inaccurate polygon in the cutout, which could be fixed fairly easily.



You could also clean up your cutout mesh, but it's not worth the work. I recommend making a more accurate and stable mesh, using the following steps:


Create a cylinder (shift+a).
Go to edit mode (tab).
Turn on proportional editing o, and change the mode to sharp.
Select the top, center vertices, and scroll the mouse wheel while grabbing them (g) until you have the desired result.
Do the same for the bottom.


Here is an animation demonstrating the process.



To perform the cut, use the following steps:

Add a boolean modifier and set it to difference.


Select the mesh which needs the hole in it. (not the mesh to make the hole!)
Go to the modifiers tab and add a boolean modifier.
Set the type to difference, and the object to the shape to make the hole (your heart shape).
Apply the modifier.
Select and delete the heart shape (or just move it away).


There now should be a heart shaped hole in the mesh.







If you want another option, enter edit mode (tab), add a little more geometry (ctrl+r for loop cut) and use the cut out tool (k) to manually cut out the geometry. Before doing this you will want to switch to orthographic view (numpad 5) and top view (numpad 7) to get the proper cuts. Then disable limit selection to visible (see image) so it will cut all the way through the mesh, and click where you would like to cut. When you are done, press enter to finish the cut. If you would like to cancel push esc. I hope this helps.





Here is my blend file.