Basic definitions:

Upper and lower asymptotic density (a.k.a. natural density):

$$\overline d(A)=\limsup \frac{A(n)}n$$

$$\underline d(A)=\liminf \frac{A(n)}n$$

Upper and lower uniform density (a.k.a. Banach density):

$$\overline u(A)=\lim_{s\to\infty} \max_{t\ge 0}\frac{A(t+1,t+s)}{s}$$

$$\underline u(A)=\lim_{s\to\infty} \min_{t\ge 0}\frac{A(t+1,t+s)}{s}$$

where $A(m,k)=|A\cap\{m,m+1,\dots,k\}|$ and $A(n)=A(1,n)$.

Note that $\underline d(\mathbb N\setminus A)=1-\overline d(A)$ and $\underline u(\mathbb N\setminus A)=1-\overline u(A)$.

It is known that $\underline u(A)\le \underline d(A) \le \overline d(A) \le \overline u(A)$, see e.g. [GLS].

The condition that $d_n$ is unbounded is equivalent to $\underline u(A)=0$.

(If $d_n$ is unbounded that we can found arbitrarily large $s$ with $A(t+1,t+s)=0$. On the other hand, if $d_n\le M$, then $A(t+1,t+s) \ge \left\lfloor\frac{s}M\right\rfloor$ and $\underline u(A)\ge \frac 1M$.)

It is known that $\overline u(A)=\sup\{\mu(A); \mu\text{ is a shift-invariant mean on }\mathbb N\}$. The proof of this fact can be found in [B]. (EDIT: Now I realized that you have seen this result in an answer to another your question Invariant means on the integers Both [B] and this answer concern invariant means on $\mathbb Z$ and not $\mathbb N$, but this should not make much difference.)

Knowing all of this, you in fact ask whether $\underline u(A)=0$ implies $\overline d(A)=0$ or even $\overline u(A)=0$. Many counterexamples can be found. Just one of them: For the set

$$A=\mathbb N\setminus \bigcup_{k=1}^\infty \{10^k+1,\dots,10^k+k\}$$

we get $\underline u(A)=0$ and $\underline d(A)=\overline d(A)=\overline u(A)=1$.

~~(If I remember correctly, I have seen the result that for any choice of $0\le a \le b \le c \le d\le 1$ there exists a set $A$ such that the values of $\underline u(A)$, $\underline d(A)$, $\overline d(A)$, $\overline u(A)$ are $a$, $b$, $c$ and $d$, respectively; but I might be mistaken and I cannot find any reference right now. Maybe I mixed it up with a similar result for some other type of densities.)~~

EDIT: The question whether the result mentioned in preceding paragraph holds is now posted on MO as a separate question: On the independence of lower and upper asymptotic and Banach densities

Perhaps I should mention that several equivalent definitions of Banach/uniform density appear in the literature. They are compared e.g. in [GTT]. (E.g. [B] works with a different - but equivalent - definition.)

Some references to papers where this notion was studied under the name uniform density are given in [GLS]. If I am not mistaken, the term Banach density was coined by Furstenberg [F].

[B] Mathias Beiglbock: An ultrafilter approach to Jin’s Theorem
http://www.mat.univie.ac.at/~mathias/UltraJin_final.pdf

[F] H. Furstenberg. Recurrence in ergodic theory and combinatorial number theory. Princeton University Press, Princeton, 1981.

[GLS] Z. Gáliková, B. Lászlo and T. Šalát: Remarks on uniform density of sets of integers
http://www.emis.ams.org/journals/AMI/2002/acta2002-galikova-laszlo-salat.pdf

[GTT] Georges Grekos, Vladimír Toma and Jana Tomanová. A note on uniform or Banach density.
http://ambp.cedram.org/ambp-bin/fitem?id=AMBP_2010__17_1_153_0

`$\mathbb N$`

into two pieces both of which have unbounded`$d_n$`

's; where one piece has a big gap to make its`$d_n$`

big, the other has a run of consecutive 1's. That prevents any non-trivial mean (invariant or not) from being 0 on all such sets. (I suspect that number theorists will object to the "number theory" tag.) $\endgroup$ – Andreas Blass May 27 '11 at 14:10