Why can I not tile any rectangle without gaps with the given shape?
http://i.stack.imgur.com/9oxO4.png
You can mirror the shape (i.e. turn it around an axis in its own plane by $\pi$).
[Math] Covering any rectangle with this shape is not possible
tiling
Related Solutions
Yes, it is always possible.
Suppose $n>3$ is odd. Then we arrange the polygons as shown (examples below for $n=5,7,9$):
Note also that $n=3,4$ are trivially possible.
Now suppose $n>4$ is even. Then we take the construction from $n/2$ (which we may assume exists by induction) and simply truncate the corners of the $n/2$-gons to produce $n$-gons which share the same adjacency graph, while causing equal perturbations to the "holes" so that they remain congruent to one another.
Best Answer
Now that's a nice question indeed. At first glance, it is not clear at all why the shape can't tile a rectangle. After all, it can obviously tile the plane. Moreover, it can even tile a rectangular shell:
That's where parity kicks in.
Quite apparently, a rectangle has none of those diagonal ears dangling outside, which means they all must be coupled with similar ears of other shapes. In this manner, each shape is "connected" to two others, and the whole figure (rectangle or whatever else) becomes a cycle, or maybe a union of several disjoint cycles. Let's look closer at one such cycle.
Let's mark the midpoints of all $\sqrt2$-length sides and join them sequentially. That would give us a cyclic path, or a polygon. Being composed of diagonal sides, it is a union of $\sqrt2\times\sqrt2$ squares, and as such, has even area. Let's remember that for later use.
Now, each of the shapes forming the cycle sits on the path and is cut by it in two unequal parts with areas $1\over4$ and $7\over4$. Some have their greater part inside the path, and some outside; let's call them "inner" and "outer", respectively. How many of each kind do we have?
Let's sum up the angles of the path, as if it were a polygon. Say, it has $n$ edges. For obvious parity reasons, $n$ must be even: $n=2k$. (This, BTW, does indeed enforce the checkerboard pattern envisioned by Dan Rust, albeit only within one cycle; not that it helped us much in evading the corners of a rectangle!) Let's look from the inside. Then every inner shape touches two vertices(*) and contributes $3\pi\over2$ to the sum, while every outer one touches just one vertex and contributes $\pi\over2$. On the other hand, the sum of all angles is known to be $\pi(n-2)$.
(*) Other points where the shapes touch or cross the path do not count. On the contrary, the vertices where the path goes straight (which, strictly speaking, are not corners) still do count, as if they were the angles of $180^\circ$.
The rest is simple: to match the sum of angles, we must have $k-2$ inner shapes and $k+2$ outer ones. Thus the sum of their parts inside the path takes up ${7\over4}(k-2)+{1\over4}(k+2)=2k-3$, which is odd. So the unoccupied space inside the path has odd area, and therefore can't be empty.
Q.e.d.