Propositions solve puzzles

Bill has lately been writing about propositions.  Correspondent Jacques writes that he finds the literature on propositions confusing and frustrating.  Propositions, he feels, have no explanatory value.  But proposition talk seems to make sense to Bill.  At one point he raises Frege's puzzle:

Tom believes that Cicero is a Roman; Cicero is Tully. But Tom does not believe that Tully is a Roman. Is there not a genuine puzzle here the solution to which will involve a theory of propositions?

My thought is that there is a problem here only for certain kinds of theory of the proposition.  Tom's situation is sufficiently common that we ordinarily do not find it puzzling at all.  The explanation is simple:  Tom has heard of a man called 'Cicero' and knows that he is a Roman.  Tom hasn't heard of a man called 'Tully', or if he has then he's heard nothing to suggest that Tully is a Roman.  Tom doesn't know that 'Tully' is another name for Cicero.  Why is it puzzling that he lacks a belief in this Tully's Roman-ness?  Bill has things back to front:  Propositions don't solve this puzzle---they are the source of the puzzle.