Solution deployed in Central Administration, but Web Part missing

I have WebApp at URL http://AUrl/

I have deployed solution with single file in _layout. And then removed that solution and installed upgrade with new web part in it.

I can see in Central administration that my solution is deployed to http://AUrl/

I can not see that web part on http://AUrl/site/SomeSiteHere.

Any ideas?

PS I do not have any actual content under http://AUrl/ accessible via web browser.