Blender

Blender is exporting corrupt obj and stl files. Shapeways just won't read them. It's not just Shapeways either. (I've gone so far as to try uploading to other 3D printing services with the same problem) Its strange because I can open them in Microsoft 3D builder. I just can't upload them (also my internet is fine). Anyone know whats up?

Try loading them into (free, cross-platform) netfabb studio basic to see what is wrong with them. Does it happen with very simple geometries (single sphere or box) as well ?

Which version of Blender are you using? Is it the latest release, or an earlier one? Either way, try importing the models into Meshlab, then export as STL or OBJ from there. Usually, Meshlab (a free software package) will automatically correct issues with corrupted geometry files, and turn around and export sound objects that can be opened virtually anywhere.

It's the unit of measure that is in use at the time of the export.
Convert your objects dimensions to METERS in blender, export your STL, then scale your object within Shapeways back to cm or mm as need be.

You could also simply set the object dimensions to mm or cm directly in Blender before export. There's no specific mm setting, but if you use Metric, setting the scale value to 0.001 will implement millimeters for the scene units scale.

If you do that in the default scene (enable Metric with 0.001), the helper grid disappears. It seems to require tweaks in other places. Also, taking into account how computer are not precise by default (int/float vs bignum), could it cause math errors? There is already one case (VRML files) in which ignoring numerical representation damaged models.

The helper grid isn't disappearing, it's just scaling up past your frame of view, because you most likely have other elements in the scene which are using the default metric scale to begin with. For example, if you open the default scene in Blender, and switch the scene scale units to Meters, then scale the default scene to 0.001, the default cube is rescaled 1000x smaller than the grid units which are still set to meters. So the grid appears to vanish, but it's still there. Tap "N" on your keyboard to bring up the Properties panel. Open the "Display" dropdown panel, and change the Grid Floor scale to 0.001 also. now the grid will appear as per normal in the scaled scene.

Edit to say: I would recommend setting these scale changes to your scene BEFORE modeling an object for export to 3d print. Rescaling the elements in your scene, which may have been modeled to Meters, or Blender Generic Units, could cause problems. Scale your scene to millimeters first, before you begin the model. I have to also give a word of warning that not all of Blender's parameters respect Metric unit scale. This has been a issue with modeling things to scale in Blender, and one reason I continue to use 3dsmax as my primary modeling package. It may not impact every model, but many of the tools in Blender will display generic numerical input values, and not scene scale values. Just a warning.

That is why post says "needs more tweaks". It also says "default scene", the dumb cube from a new install (testing 2.77a). Grid one was the obvious "still something else affected". Other tools also assume units are meaningless, and for some cases they fail or give poor control. Which is what you mean with "not all of Blender's parameters respect Metric unit scale". Units are an afterthought in Blender and yet to be finished.

Being using Blender for ages, way before than units were implemented, plain old "it works" was: decide unit to use that keeps things around 1, model in that, upload in that. For common SW models (= small) best use mm, so 1BU 1mm, and upload in mm. Or similar with inches if so inclined. It hurts more than helps, specially if disciplined in metric tech drawing (same sheet mixing 1m and 0.1mm? recipe for disaster when 1000 and 0.1 works). Way easier to remember one thing than figuring why Blender is doing "funny things".