QGIS Graphics Glitch after changing CRS

I loaded the Natural Earth Quick Start Kit in QGIS 2.8.5, enabled on-the-fly CRS transformation, and changed the CRS to World_Robinson, and this is what shows up:

When zoomed in it looks fine. To be precise, the glitch start to happen somewhere between 1:45,000,000 and 1:46,000,000.

Any idea what's causing this? Am I doing something wrong here?

EDIT: I don't think this is a duplicate issue. At least the "Settings -> Options, Rendering tab, uncheck Enable feature simplification by default for newly added layers" fix does nothing for this problem.

EDIT 2: This isn't limited to Robinson. Pretty much every CRS I tried has graphical glitches when viewing the whole world. And every CRS works fine when zoomed in (at 1:20,000,000 everything works).

Answer

I've seen this a few times with Robinson and similar projections. Artifacts like these are caused by polygons which cross the antimeridian (180 degrees west). This happens on some, but not all, of the Natural Earth shapefiles.

Here's the 10m scale provinces from Natural Earth Starter kit, you can see the artifacts. Zooming in removes these, because the problem polygons now fall outside the drawing area (canvas extent) so they aren't drawn.. This is why the problem is scale-dependent.

Quickest way to fix this is to call ogr2ogr with the -wrapdateline option. This makes sure everything gets clipped to the antimeridian, and writes it to a new shapefile.

ogr2ogr -wrapdateline -t_srs EPSG:4326 /tmp/fixed_4326.shp ne_10m_admin_1_states_provinces_shp.shp

This is a command line tool, which should be installed along with QGIS.

This gave a couple of geometry errors, but still managed to write the new shapefile.

ERROR 1: TopologyException: Input geom 0 is invalid: Self-intersection at or near point 179.99999997866655 -84.515235437277511 at 179.99999997866655 -84.515235437277511
ERROR 1: TopologyException: Input geom 0 is invalid: Self-intersection at or near point 179.99999997866655 -84.515235437277511 at 179.99999997866655 -84.515235437277511

Loading in fixed_4326.shp, the problem is fixed.

(I did this in 2.12.2 Pisa, your mileage may vary with 2.8)

The other thing i see is bounding boxes (in pink). These appear as trapezoids, with straight edges. To get nice curved edges on these, you'll need to densify them. See this answer on how to densify for Robinson projection