MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 deleted 43 characters in body; added 2 characters in body

For $C_3(n)$ an absolute upper bound is $3(n-1)^2+3$ which can always be attained by taking the cubes on three faces adjacent to a given corner, removing the corner itself, and removing all but one cube on each edge incident to the corner. Unfortunately, this gives a bound of 15 in the $n=3$ case., so does not improve your particular case. Somewhat generalizing this construction to higher dimensions, for $d\geq 4$ one gets an absolute upper bound for $C_d(n)$ of

$[n^d-(n-1)^d]-d(n-1)+1$

To prove this always works, consider $C_d(n)$. We will replace each cube by its center point and consider the lattice as in Joseph's previous question which he references.

WLOG, let one corner of $C_d(n)$ be centered at the origin. The lines we want to block have $(d-1)$ coordinates fixed and one coordinate which varies. Now consider the set of all cubes whose center has at least one coordinate equal to 0; this is exactly the set of all cubes lying on one (or more) $d-1$-dimensional (d-1)$-dimensional faces adjacent to our origin cube. There are $[n^d - (n-1)^d]$ such cubes. Now remove all cubes along the edges incident to our cube centered at the origin, this removes $d(n-1)+1$ cubes leaving the set $S_d(n)$ which consists of all cubes with at least one and at most $(d-2)$ coordinates equal to 0. The only lines which do not intersect this set are those which have $(d-1)$ fixed coordinates equal to 0, i.e. the lines incident to our cube centered at the origin. Since cubes are adjacent iff they differ in exactly one coordinate, it is easy to check that the $S_d(n)$ is connected for $d\geq 4$ but not connected for $d=3$. So we need only add our cube centered at the origin, and one cube adjacent to it to block the remaining lines while ensuring the entire collection is connected.

Note that if the above held for $d=3$, one could use it to push our bound down from Joseph's 15 to 14; however the set $S_3(n)$ consists of 3 disconnected pieces and so the reasoning leading to this formula fails. However this formula does imply that as $d$ or $n$ gets large, one can block all lines with an arbitrarily small fraction of all available cubes.

There might be is probably a way to do some more inclusion-exclusion to further eliminate some particular pieces of the lower dimensional planes incident to our cube centered at the origin $S_d(n)$ as unnecessary for blocking purposes and thereby further reduce our bound, but offhand I don't see it.
show/hide this revision's text 1

For $C_3(n)$ an absolute upper bound is $3(n-1)^2+3$ which can always be attained by taking the cubes on three faces adjacent to a given corner, removing the corner itself, and removing all but one cube on each edge incident to the corner. Unfortunately, this gives a bound of 15 in the $n=3$ case., so does not improve your particular case. Somewhat generalizing this construction to higher dimensions, for $d\geq 4$ one gets an absolute upper bound for $C_d(n)$ of

$[n^d-(n-1)^d]-d(n-1)+1$

To prove this always works, consider $C_d(n)$. We will replace each cube by its center point and consider the lattice as in Joseph's previous question which he references.

WLOG, let one corner of $C_d(n)$ be centered at the origin. The lines we want to block have $(d-1)$ coordinates fixed and one coordinate which varies. Now consider the set of all cubes whose center has at least one coordinate equal to 0; this is exactly the set of all cubes lying on one (or more) $d-1$-dimensional faces adjacent to our origin cube. There are $[n^d - (n-1)^d]$ such cubes. Now remove all cubes along the edges incident to our cube centered at the origin, this removes $d(n-1)+1$ cubes leaving the set $S_d(n)$ which consists of all cubes with at least one and at most $(d-2)$ coordinates equal to 0. The only lines which do not intersect this set are those which have $(d-1)$ fixed coordinates equal to 0, i.e. the lines incident to our cube centered at the origin. Since cubes are adjacent iff they differ in exactly one coordinate, it is easy to check that the $S_d(n)$ is connected for $d\geq 4$ but not connected for $d=3$. So we need only add our cube centered at the origin, and one cube adjacent to it to block the remaining lines while ensuring the entire collection is connected.

Note that if the above held for $d=3$, one could use it to push our bound down from Joseph's 15 to 14; however the set $S_3(n)$ consists of 3 disconnected pieces and so the reasoning leading to this formula fails. However this formula does imply that as $d$ or $n$ gets large, one can block all lines with an arbitrarily small fraction of all available cubes.

There might be a way to do some more inclusion-exclusion to further eliminate some of the lower dimensional planes incident to our cube centered at the origin as unnecessary for blocking purposes and thereby further reduce our bound, but offhand I don't see it.