<PAGE>
 
                                                                   EXHIBIT 10.40

                     AMENDED AND RESTATED LETTER AGREEMENT
                     -------------------------------------

     This Amended and Restated Letter Agreement ("Agreement") is made and
entered into as of February 5, 1999, by and among CellStar, Ltd. ("CellStar"),
CellStar Telecom, Inc. ("CellStar Telecom") (CellStar and CellStar Telecom are
hereinafter sometimes collectively referred to as the "CellStar Parties"), Topp
Telecom, Inc. ("Topp Telecom"), David Topp, Dora Topp, Risia Topp Wine, Mark
Topp and F.J. Pollak (Topp Telecom, David Topp, Dora Topp, Risia Topp Wine and
Mark Topp and F.J. Pollak are hereinafter sometimes collectively referred to as
the "Topp Parties").  The CellStar Parties and the Topp Parties are hereinafter
collectively referred to as the "Parties."

                              W I T N E S S E T H:
                              --------------------

     A.  The Parties are parties to that certain Letter Agreement, dated
September 1, 1998 (the "September Agreement"), as amended by Amendment to
September 1st Letter Agreement, dated December 18, 1998 (the "December
Agreement" and collectively with the September Agreement, the "Original
Agreement").

     B.  The Parties desire to amend and restate the Original Agreement, upon
the terms and conditions as hereinafter set forth.

     C.  This Agreement is being entered into in connection with that certain
Stock Purchase Agreement, dated the date hereof, in which Inmobiliaria Aztlan,
S.A. de C.V., a wholly owned subsidiary of Telefonos de Mexico, S.A. de C.V.
will purchase a controlling interest in Topp Telecom (the "Tel Mex Purchase
Agreement").

     D.  The consummation of the transactions contemplated by this Agreement are
conditioned upon, and shall occur simultaneous with, the closing of the Tel Mex
Purchase Agreement (the "Closing Date").

     E.  Topp Telecom currently has authorized capital stock of (i) 5,000,000
shares of voting common stock, $.01 par value (the "Voting Common Stock"), of
which 6,100 shares are outstanding, (ii) 5,000,000 shares of non-voting common
stock, $.01 par value (the "Non-Voting Common Stock"), of which 133,463 shares
are outstanding, (iii) 1,043 shares of Class A Convertible Preferred Stock, $.01
par value ("Series A Preferred"), of which 100 shares are outstanding, and (iv)
17,988 shares of Class B Convertible Preferred Stock, $.01 par value ("Series B
Preferred"), of which 100 shares are outstanding.

     F.  Topp Telecom currently owes a principal amount of approximately
$26,990,000 to CellStar pursuant to a Promissory Note, dated as of September 1,
1998, in the principal amount of up to $26,990,000, as amended by the December
Agreement (the "Original Note").

     G.  On the Closing Date, as a result of the exercise of the Option by
CellStar, as described herein, the principal balance of the promissory note
shall be reduced by the exercise price of the Option.
<PAGE>
 
     H.  On the Closing Date, David Topp (and his family members, pro rata),
will purchase (pursuant to an endorsement thereof) an aggregate amount of 10% of
the principal amount of the promissory note, or $2,499,000, resulting in a
$22,507,537 principal amount owed by Topp Telecom to CellStar.

     I.  The capitalized terms contained but not defined herein shall have the
meanings ascribed to them in the Original Agreement.

     NOW, THEREFORE, in consideration of the premises and mutual covenants set
forth herein, and other good and valuable consideration, the receipt and
sufficiency of which are hereby acknowledged, each of the undersigned Amendment
Parties hereby agree as follows:

                                   AGREEMENT
                                   ---------

     1.  Amended and Restated Credit Facility Note; Purchase by Topp Group. On 
         ----------------------------------------------------------------- 
the Closing Date, Topp Telecom shall execute and deliver divided replacement
notes to CellStar in the aggregate principal amount of $24,990,000 that reduce,
divide and amend the Original Note as follows (collectively, the "Divided
Replacement Notes"): (i) a Divided Replacement Note in the principal amount of
$22,507,537 in the form and containing the terms and conditions of the Note set
forth as Exhibit A, and (ii) Divided Replacement Notes in the aggregate
principal amount of $2,499,000. On the Closing Date, each of David Topp, Dora
Topp, David and Dora Topp as joint tenants, Mark Topp and Risia Topp Wine
(collectively, the "Topp Group") will pay to CellStar, pro rata, an aggregate of
$2,499,000 in immediately available funds in exchange for the assignment and
endorsement by CellStar to: (i) David Topp of a replacement note, in the form
and containing the terms and conditions of the Note set forth in Exhibit B in
                                                                 ---------
the principal amount of $838,165; (ii) Dora Topp of a replacement note, in the
form and containing the terms and conditions of the Note set forth in Exhibit C
                                                                      ---------
in the principal amount of $837,165; (iii) David and Dora Topp, as joint tenants
with right of survivorship, of a replacement note, in the form and containing
the terms and conditions of the Note set forth in Exhibit D in the principal
                                                  ---------
amount of $265,394; (iv) Mark Topp of a replacement note, in the form and
containing the terms and conditions of the Note set forth in Exhibit E in the
                                                             ---------
principal amount of $279,138; and (v) Risia Topp Wine of a replacement note in
the form and containing the terms and conditions of the Note set forth in
Exhibit F in the principal amount of $279,138, each without recourse,
---------   
representation or warranty of any kind whatsoever, and subject to any and all
defenses, counterclaims and setoffs of Topp Telecom as to payment of principal
or interest on, or performance of any other obligation under, the Original Note
or said Divided Replacement Notes. Upon delivery of the Divided Replacement
Notes to CellStar, CellStar shall return the executed Original Note to Topp
Telecom, marked cancelled. Paragraph 4 of the December Agreement is hereby
amended to change the date of February 15, 1999 to reflect the earlier of (x)
the termination of the Purchase Agreement (but in no event earlier than February
15, 1999), or (y) March 1, 1999, in each place where such February 15 date is
referenced in paragraph 4.

     2.  Termination Security Interests.  On the Closing Date, all security 
         ------------------------------
for the Note shall be terminated, and, to evidence such termination, CellStar
shall deliver (a) to Topp Telecom manually executed originals of (i) Form UCC-3
termination statements terminating the security

                                       2
<PAGE>
 
interests granted by Topp Telecom to CellStar (or its affiliates) as evidenced
by Form UCC-1, file number 980000197088, filed with the Florida Secretary of
State, and Form UCC-1, the number 970000236679, filed with the Florida Secretary
of State, (ii) Security Agreement, dated as of September 1, 1998, between Topp
Telecom and CellStar, marked cancelled, and (iii) Power of Attorney, dated as of
September 1, 1998, delivered by Topp Telecom in favor of CellStar, marked
cancelled; (b) to David Topp manually executed originals of the (i) Stock Pledge
Agreement, dated as of September 1, 1998, between David Topp (on behalf of
himself and Dora Topp, Risia Topp Wine and Mark Topp) in favor of CellStar,
marked cancelled, (ii) Stock Certificate No. 1 representing 26,000 shares of 
Non-Voting Common Stock issued to David Topp, along with Stock Power regarding
such shares in favor of CellStar marked cancelled, (iii) Stock Certificate No. 3
representing 30,000 shares of Non-Voting Common Stock issued to Dora Topp, along
with Stock Power regarding such shares in favor of CellStar marked cancelled,
(iv) Stock Certificate No. 4 representing 10,000 shares of Non-Voting Common
Stock issued to Mark Topp, along with Stock Power regarding such shares in favor
of CellStar marked cancelled, (v) Stock Certificate No. 5 representing 10,000
shares of Non-Voting Common Stock issued to Risia Topp Wine, along with Stock
Power regarding such shares in favor of CellStar marked cancelled, (vi) Stock
Certificate No. 11 representing 9,516 shares of Non-Voting Common Stock issued
to David and Dora Topp, along with Stock Power regarding such shares in favor of
CellStar marked cancelled, (vii) Stock Certificate No. 1 representing 4,000
shares of Voting Common Stock issued to David Topp, along with Stock Power
regarding such shares in favor of CellStar marked cancelled, and (viii)
Irrevocable Proxy Agreement, dated as of September 1, 1998, among CellStar,
David Topp, Dora Topp, Risia Topp Wine and Mark Topp, marked cancelled; and (c)
to F.J. Pollak manually executed originals of (i) Stock Pledge Agreement, dated
as of September 1, 1998, between F.J. Pollak and CellStar, (ii) Stock
Certificate No. 2 representing 1,000 shares of Voting Common Stock, along with
Stock Power regarding such shares in favor of CellStar marked cancelled, (iii)
Stock Certificate No. 2 representing 19,000 shares of Non-Voting Common Stock,
along with Stock Power regarding such shares in favor of CellStar marked
cancelled, and (iv) Irrevocable Proxy Statement, dated as of September 1, 1998,
between CellStar and F.J. Pollak, marked cancelled; provided, that, in the event
CellStar fails to deliver the executed originals of any instruments referenced
in items (a)(ii) and (iii), b(i) and (viii), or (c)(i) and (iv), the parties
acknowledge that, notwithstanding their failure to deliver, all such instruments
will be terminated as of the Closing Date, and no party thereto shall have any
rights, obligations or liabilities with respect thereto, all of which shall have
been deemed to be fully released.

     3.  Termination of Guarantees.  On the Closing Date, all personal 
         -------------------------
guarantees for the Note shall be terminated and, to evidence such termination,
CellStar shall deliver to David Topp and F.J. Pollak the manually executed
original Guaranty, dated as of September 1, 1998, marked cancelled, and no party
thereto shall have any rights, obligations or liabilities with respect thereto,
all of which shall have been deemed to be fully released.

     4.  Distribution Agreement.  On the Closing Date, the Distribution and
         ----------------------                                            
Fulfillment Agreement, by and between CellStar and Topp Telecom, dated as of the
15th day of September 1997, as amended by that certain Amendment to Distribution
and Fulfillment Agreement, dated as of September 1, 1998, and further amended as
set forth in the December Agreement, shall be 

                                       3
<PAGE>
 
further amended in the form attached hereto as Exhibit G. Topp Telecom and
CellStar intend to amend and restate the Distribution Agreement within the next
20 business days after the Closing Date to more accurately reflect the status of
their business relationship after giving effect to the Tel Mex Purchase
Agreement.

     5.  License Agreement.  Effective on the Closing Date, the Amended and 
         -----------------
Restated License Agreement, dated as of September 1, 1998, shall be terminated.

     6.  Exercise of Options and Warrants and Conversion of Preferred Stock; Net
         -----------------------------------------------------------------------
Amounts Owed to CellStar.  On the Closing Date, CellStar shall (a) exercise in
------------------------                                                      
full the Option by offsetting the principal due under the Original Note in the
amount of $1,978,982, (b) exercise in full the Warrant by receiving credit in
the amount of $2,643, and (c) convert the 100 shares of Series A Preferred Stock
and 100 shares of Series B Preferred Stock into 100 shares of Voting Common
Stock and 100 shares of Non-Voting Common Stock, respectively.  On the Closing
Date, Topp Telecom shall (upon receipt of the consideration referenced above, as
well as the certificates representing the shares of Series A and Series B
Preferred Stock), deliver (i) a stock certificate to CellStar for the number of
shares of Voting Common Stock and Non-Voting Common Stock as set forth on the
Closing Memorandum attached hereto as Exhibit H.
                                      --------- 

     7.  Amendment to Articles of Incorporation.  On the Closing Date, the 
         -------------------------------------- 
Articles of Amendment to the Articles of Incorporation which, among other
things, delete the classes of Series A and Series B Preferred Stock, shall be
filed with the Florida Secretary of State, a form of which are attached hereto
as Exhibit I.
   --------- 

     8.  Mutual Releases.  On the Closing Date, each Release and Waiver as set 
         ---------------
forth in Exhibit J-1 and J-2 shall be executed and delivered by the parties
thereto.

     9.  Interest on Original Note.  On the Closing Date, Topp Telecom will pay
         -------------------------                                             
accrued interest as of such date under the Original Note based on an outstanding
principal amount of $26,990,000, it being understood that Topp Telecom and
CellStar shall negotiate in good faith to determine the actual amount of such
principal for calculation of the interest payment and to pay (or receive credit
against any future interest payment), as the case may be, within five days of
such final determination.

     10. Governing Law.  This Agreement shall be governed by and construed in
         -------------                                                       
accordance with the laws of the State of Florida, without regard to the
principles of conflicts of laws thereunder.

     11. Benefit.  This Agreement shall be binding upon and inure to the 
         -------
benefit of each of the parties hereto and each of their respective successors
and permitted assigns.

     12. Counterparts.  This Agreement may be executed in any number of
         ------------                                                  
counterparts, with each counterpart constituting an original, but altogether
constituting but one and the same agreement.

                                       4
<PAGE>
 
     13.  Attorneys Fees.  In the event that there shall be any dispute 
          --------------
relating to or arising out of or in connection with this Agreement, the
prevailing party shall be entitled to recover from each of the other adverse
parties thereto, jointly and severally, attorneys' fees and costs incurred, at
all levels.

     14.  Drafting.  This Agreement has been drafted with the suggestions and
          --------                                                           
revisions of all parties hereto and should not be construed more strictly
against one party than against any other.

     15.  Cooperation.  Each party hereto agrees to execute and deliver, upon 
          -----------
the request of any other party hereto and in addition to the documents to be
delivered pursuant hereto, such documents as may be reasonably necessary to
evidence or effectuate the terms and conditions of this Amendment and to comply
with applicable law.

     16.  Amendments.  This Agreement may not be amended or modified except 
          ----------  
pursuant to a written instrument executed by all parties hereto.

     17.  Termination of this Agreement and Survival of Original Agreement.  
          ----------------------------------------------------------------
This Agreement shall terminate in the event the Purchase Agreement is terminated
pursuant to Article XV thereof.

     18.  Conditions of Performance.  The covenants of the parties contained 
          -------------------------
herein are dependent and the performance of each obligation to be performed on
the Closing Date is conditioned on the performance of all obligations required
to be performed on the Closing Date under this Agreement and the Telmex Purchase
Agreement.

                                       5
<PAGE>
 
     IN WITNESS WHEREOF, this Agreement is entered into as of the date first
above written.

CellStar, Ltd.                                  CellStar Telecom, Inc.
By:  National Auto Center, Inc.
Its:  General Partner
 

/s/ ELAINE FLUD RODRIGUEZ                       /s/ ELAINE FLUD RODRIGUEZ
----------------------------------              -------------------------------
By:  Elaine Flud Rodriguez                      By:  Elaine Flud Rodriguez  
Its: Vice President                             Its: Vice President         


Topp Telecom, Inc.


/s/ F.J. POLLAK                                 /s/ DAVID TOPP                  
----------------------------------              --------------------------------
By:  F.J. Pollak                                David Topp
Its: President


/s/ DAVID TOPP                                  /s/ DAVID TOPP
----------------------------------              --------------------------------
David Topp, as attorney-in-fact for             David Topp, as attorney-in-fact
Dora Topp                                       for Risia Topp Wine
 
/s/ DAVID TOPP                                  /s/ F.J. POLLAK  
----------------------------------              --------------------------------
David Topp, as attorney-in-fact for             F.J. Pollak
Mark Topp 


Acknowledged:
 
Telefonos de Mexico, S.A. de C.V.
 
/s/ ADOLFO CEREZO 
----------------------------------
By:  Adolfo Cerezo 
Its: C.F.O.

                                       6