New post under custom post type doesn't appear at the category assigned.

I created a new post type named "Products". I created a new post there and I assigned it to a couple of categories as seen at the screenshot below:

When I visit this post-product's page it is perfect and the categories are there, too (take a look at the bottom-left corner of the screenshot below):

Because I know that "it's all Greek to you", the categories read "??????, ?????? ????????, ????? ?????????". The problem is that when I click at the category link ie. ?????? this new post does not appear there.

Any ideas?

Unfortunately this is not a live website yet, so you could possibly visit it only if you add it's IP at the hosts file. If you need to do so just let me know.