Schönhardt Polyhedron
This shape was described by E. Schönhardt, "Über die
Zerlegung von Dreieckspolyedern in Tetraeder", Math. Annalen
98 (1928) 309312. It is combinatorially an octahedron, twisted so that
three of its dihedrals are concave. Each vertex is connected by edges
to four others, but the diagonal to the remaining vertex always passes
outside the polyhedron, so there is no way to place a diagonal inside
partitioning the shape into tetrahedra.
One consequence is that, although the region
CH(P u Q)(P u Q)
between two convex polyhedra P and Q can always be tetrahedralized
[J. E. Goodman and J. Pach, "Cell decomposition of polytopes by bending",
Israel J. Math. 64 (1988) 129138],
the region between three cannot (the Schönhardt polyhedron can be
expressed as the region between three tetrahedra).

Thurston Polyhedron
This shape (not the colored blocks, but the region of space surrounding
them) was used by M. S. Paterson and F. F. Yao,
"Binary partitions with applications to hiddensurface removal and solid
modeling", Proc. 5th ACM Symp. Comp. Geom. (1989) 2332,
to show a lower bound on the complexity of subdividing an axisparallel
polyhedron into convex regions.
Three sets of cuboids interlace to surround
Omega(n^{3/2}) cubical voids, each of which must occupy a
separate component in any convex decomposition.
The point in the center of each void can not see any
vertices, so the shape is untetrahedralizable.
Paterson and Yao credit
this application of the shape to a personal communication by
W. P. Thurston, but the shape itself has been seen before e.g.
in Alan Holden's book Shapes, Space, and Symmetry (Columbia
Univ. Press 1971) p. 161. Holden also describes a related interlocked
lattice of triangular prisms with rhombicdodecahedron voids. 
Chazelle Polyhedron
This shape is formed by removing wedges from a cube.
The upper wedges have their edges on lines of the form
y = xz + epsilon,
z = const
and the lower wedges have their edges on lines of the form
y = xz  epsilon,
x = const,
so the hyperboloid y = xz is approximated
on one side by ridges parallel to the xy plane, and on the other side by
ridges parallel to the yz plane.
B. Chazelle, "Convex partitions of polyhedra: a lower bound and
worstcase optimal algorithm", SIAM J. Comput. 13 (1984) 488507,
showed that this example can not be partitioned into fewer than
Omega(n^{2}) convex pieces.
As I pointed out to Paterson and Yao, this same example
solves an open problem from their paper on the complexity of
threedimensional binary space partitions. 