How should I establish initial contact with ATC after being handed off by another controller? What is the proper way to contact a new air traffic control facility after you have be instructed to do so by the controller you are currently interacting with?

As a practical example: Here in Northern California, I will typically contact NorCal Approach on 125.4 to get flight following. If I travel ~50 miles north, approach will tell me to contact Oakland Center on 132.2. When I contact Oakland Center, what is the proper way to announce myself?

My original CFI instructed me to say:


  Oakland Center, Tail Number, with you on 132.2


However my new CFI, says that is incorrect and in fact alluded to the idea that perhaps it was ridiculous. His instructions were:


  Oakland Center, Tail Number


However, the two times I had used the more abbreviated version above, the controller seemed unsure of my intentions and I had to state (in plain english because I was not sure how to communicate this) "NorCal Approach just sent me over to you".

What is the proper way to handle this situation?
In your situation:

Oakland Center, Aircraft Identification, Altitude

For example:

Oakland Center, Cessna 123AB, Level four thousand fife hundred.

See Aeronautical Information Manual, 5-3-1: ARTCC Communications.

b. ATC Frequency Change Procedures.
2. The following phraseology should be utilized by pilots for establishing contact with the designated facility:
(a) When operating in a radar environment: On initial contact, the pilot should inform the controller of the aircraft’s assigned altitude preceded by the words “level,” or “climbing to,” or “descending to,” as appropriate; and the aircraft’s present vacating altitude, if applicable.
EXAMPLE-
1. (Name) CENTER, (aircraft identification), LEVEL (altitude or flight level).
2. (Name) CENTER, (aircraft identification), LEAVING (exact altitude or flight level), CLIMBING TO OR DESCENDING TO (altitude of flight level).
NOTE-
Exact altitude or flight level means to the nearest 100 foot increment. Exact altitude or flight level reports on initial contact provide ATC with information required prior to using Mode C altitude information for separation purposes.
(b) When operating in a nonradar environment:
(1) On initial contact, the pilot should inform the controller of the aircraft’s present position, altitude and time estimate for the next reporting point.
EXAMPLE-
(Name) CENTER, (aircraft identification), (position), (altitude), ESTIMATING (reporting point) AT (time).
(2) After initial contact, when a position report will be made, the pilot should give the controller a complete position report.
EXAMPLE-
(Name) CENTER, (aircraft identification), (position), (time), (altitude), (type of flight plan), (ETA and name of next reporting point), (the name of the next succeeding reporting point), AND (remarks).
REFERENCE-
AIM, Position Reporting, Paragraph 5-3-2.