ちょっと違うかもしれませんが、DropboxやPidgin、Thunderbirdなどをスタートアップに入れても
起動に失敗することが多発しまして、その対策として、アプリを直接スタートアップするのではなく、
以下のようなスクリプトを書いてスタートアップに登録することで回避できました。

---

#!/bin/sh

while [ ! $gip ]
do
    sleep 10s
    gip=`wget -q -O - ipcheck.ieserver.net`
done

skype &

---

オンラインかどうかを10秒毎に確認して、オンラインになったらスカイプ起動です。
時間稼ぎで他の処理に圧迫？されるのを防ぎます。

たとえば、
$ gedit startup.sh
で、上記（#!/bin/sh 〜 skype &）をコピペ
$ chmod +x startup.sh
で、startup.sh をスタートアップに登録。

スタートアップの時点ではない通常時の起動できちんとアイコンが表示されるようでしたら、お試しを。