[bojan]

Yep, this is lens issue.
While being excellent for everyday photography, most lenses do no pass the ultimate test on stars, especially fast zoom lenses.
Try what Rick is suggesting, only one stop down could make a big difference.