A public synonym does not mean that grants are not required from the schema in which the parent table lies(if the synonym and the table lies in two different schemas, that is). You need to clarify your concept of public synonyms :) .
But thats not the point here.
just do:
SELECT * SOME_TABLE"@"CONNECTION_TO_ANOTHER_DATABASE;
If this gives you ORA-XXXX: Table or view doesnot exist, then this is the cause.
There are two possibilities:
1.CONNECTION_TO_ANOTHER_DATABASE has got corrupted/doesnot exist.
You can check this by doing queries like :
Select sysdate from duals@CONNECTION_TO_ANOTHER_DATABASE;
Select * from user_objects@CONNECTION_TO_ANOTHER_DATABASE;
If this too gives you the same error then that's it, your CONNECTION_TO_ANOTHER_DATABASE is gone.
If this does not give any error and gives some valid o/p then:
2.Probably the "SOME_TABLE" at the remote database does not exist!