Your shown_layer
variable should be L.mapbox.tileLayer(selectedValue)
. Then map.removeLayer(shown_layer);
should work.
Anyway, here is an example of your code using jQuery (JSFiddle):
var map = L.map('map').setView([38.902, -77.001], 13);
map.addLayer(L.mapbox.tileLayer('examples.map-zgrqqx0w'));
var shown_layer;
$("#map-ui").change(function() {
var selected = $("#map-ui option:selected").val();
if(selected === "") return;
if(shown_layer !== undefined)
map.removeLayer(shown_layer);
shown_layer = L.mapbox.tileLayer(selected);
map.addLayer(shown_layer);
});