I've not tried to do this recently, but in the past (6 months ago) the creation of a printed map using composer and the Openlayers plugin with some (all?) of the available OSM layers often didn't work for me. The other problem was that the only way I could find to set the choice of zoom level that the printed map used was to alter the resolution in the composer. In the end, for printing one-off maps of a small area (e.g. a city), I found a much better solution. There's a web service called Bigmap (there may be others) with which you can download a single zoom level of map tiles covering a decent enough area to allow for one-off printed maps. Bigmap stitches the tiles together, and you can download a '.map' file alongside the resulting png file. Open the .map file in QGIS (as a raster layer), and this provides the georeference which will bring in the png image in the correct place.
The interface on Bigmap is a little confusing, but persevere. You're choosing the map source first. Then you move in and out on the zoom levels - the options here are to account for the fact that you may want to zoom in and out changing the map area, or in and out a zoom level while maintaining the same area. 'Enqueue' asks the service to process your request, and after a while you'll get to download the result. Watch for the 'enqueue' link greying out - this happens if you have too many tiles selected.
I've sometimes needed to ask for two or three downloads for something I'm printing - but the georeference of course means that these sit nicely next to each other.
I added some slightly clearer instructions (I hope) a few months ago within the relevant OSM wiki page here.
