Exhibit 4.1

RESTRICTED STOCK PURCHASE AGREEMENT

This Restricted Stock Purchase Agreement (this “Agreement”) is made as of June 15, 2010, between Coinstar, Inc., a Delaware corporation (the “Company”), and Paramount Home Entertainment Inc., a Delaware corporation (“Paramount”).

Reference herein is made to that certain Revenue Sharing License Agreement executed between Redbox Automated Retail, LLC, a Delaware limited liability company and a wholly owned subsidiary of the Company (“Redbox”), and Paramount, dated as of August 25, 2009, and as subsequently amended by that First Amendment and Second Amendment thereto, dated December 10, 2009 and June 15, 2010, respectively (collectively, the “License Agreement”). Capitalized terms not explicitly defined in this Agreement but defined in the License Agreement shall have the same meanings as set forth with respect to such terms in the License Agreement.

1. Restricted Stock Issuance

In connection with the License Agreement and subject to the terms and conditions of this Agreement, the Company hereby agrees to issue to Paramount 200,000 shares (collectively, the “Shares”) of the Company’s common stock, par value $0.001 per share (“Common Stock”).

The Company shall issue the Shares as soon as practicable following the date of this Agreement, and in any event within twenty (20) business days following the date that Paramount has exercised its Renewal Option under Section 3.B. of the License Agreement (the “Original Issuance Date”).

2. Vesting

2.1 Shares that have vested and are no longer subject to forfeiture according to the vesting schedule set forth below or according to the provisions of Section 2.2 are referred to herein as “Vested Shares.” Shares that are not vested and remain subject to forfeiture and the restrictions hereunder are referred to herein as “Unvested Shares.”

Provided that the Unvested Shares have not, prior to their becoming Vested Shares, been forfeited pursuant to Section 6 below, the restrictions on the Unvested Shares will lapse and the Unvested Shares will become Vested Shares and no longer be subject to forfeiture according to the following schedule:

2.2 Accelerated Vesting

All of the Unvested Shares shall automatically become Vested Shares, and the restrictions under this Agreement on such Unvested Shares will lapse and such Unvested Shares will no longer be subject to forfeiture upon the occurrence of any of the following events:

(a) a “change of control” of the Company, which shall mean for purposes of this Section: (i) a merger or consolidation of the Company with or into another corporation or other entity (with respect to which less than a majority of the outstanding voting power of the surviving or consolidated corporation is held by persons who are shareholders of the Company immediately prior to such event); (ii) the sale or transfer of all or substantially all of the properties or assets of the Company; (iii) any purchase by any party (or group of affiliated parties) of shares of capital stock of the Company (either through a negotiated stock purchase or a tender for such shares), the effect of which is that such party (or group of affiliated parties) that did not beneficially own a majority of the voting power of the outstanding shares of capital stock of the Company immediately prior to such purchase beneficially owns at least a majority of such voting power immediately after such purchase; (iv) the redemption or repurchase of shares representing a majority of the voting power of the outstanding shares of capital stock of the Company; or (v) any other change of control of fifty percent (50%) or more of the outstanding Common Stock or voting power of the Company in a single transaction or series of related transactions;

(b) a “change of control” of Redbox, which shall mean for purposes of this Section: (i) a merger or consolidation of Redbox with or into another corporation or other entity (with respect to which less than a majority of the outstanding voting power of the surviving or consolidated corporation is held by the Company or its subsidiaries); (ii) the sale, lease or transfer of all or substantially all of the properties or assets of Redbox; (iii) any purchase by any party (or group of affiliated parties) of equity in Redbox, the effect of which is that such party (or group of affiliated parties) that did not beneficially own a majority of the

voting power of Redbox immediately prior to such purchase beneficially owns at least a majority of such voting power immediately after such purchase; or (iv) any other change of control of fifty percent (50%) or more of the outstanding voting power of Redbox in a single transaction or series of related transactions;

(c) The failure of the Company and/or its Common Stock to meet the continued listing requirements for the Nasdaq market or other national stock exchange, such that the Common Stock is or will be downgraded to the OTC Bulletin Board or otherwise cease trading on such stock exchange; or

(d) upon (i) either the Company or Redbox becoming unable to pay its debts; (ii) a petition being presented or a meeting being convened for the purpose of considering a resolution for the making of an administration order, the winding-up, bankruptcy or dissolution of the Company or Redbox; (iii) the Company or Redbox becoming insolvent; (iv) a petition under any bankruptcy or analogous act being filed by or against the Company or Redbox (which petition, if filed against Redbox, will not have been dismissed by the relevant authority within thirty (30) days thereafter); (v) the Company or Redbox executing an assignment for the benefit of creditors; (vi) a receiver being appointed for the assets of the Company or Redbox; (vii) the Company or Redbox taking advantage of any applicable bankruptcy, insolvency or reorganization or any other like statute; or (viii) the Company or Redbox ceasing to conduct all or substantially all of its day-to-day business operations.

3. Transfer Restrictions

Any direct sale, transfer, assignment, encumbrance, pledge, hypothecation, conveyance in trust, gift, transfer by bequest, devise or descent, or other transfer or disposition of Unvested Shares shall be strictly prohibited and void unless the Company consents to any such transaction (with any such consent being solely at the discretion of the Company); provided, however, that Paramount may transfer Unvested Shares at any time to one or more of its U.S. affiliates upon fifteen (15) days’ prior written notice to the Company provided that any such affiliate transferee provides to the Company a written acknowledgement that it agrees to join as a party to this Agreement, including, but not limited to, agreeing to the terms, conditions, representations and obligations of Paramount.

4. Status of Participant

Upon issuance of the Shares, Paramount will be recorded as a registered stockholder of the Company with respect to the Shares. The Company and its transfer agent will promptly provide to Paramount written conformation of such issuance and recordation. Upon issuance of the Shares, Paramount will have in connection with the Shares all rights of a holder of Common Stock of the Company, including, without limitation, voting rights and rights to dividends and distributions in respect of the Shares; provided, however, that Unvested Shares will be subject to forfeiture pursuant to Section 6.

5. Securities Law Compliance; Certain Representations

5.1 The Shares to be acquired by Paramount under this Agreement will be acquired for investment for Paramount’s own account, not as a nominee or agent, and not with a view to the resale or distribution of any part thereof. Paramount has no present intention of selling, granting any participation in, or otherwise distributing the Shares. Paramount does not have any contract, undertaking, agreement or arrangement with any person or entity to sell, transfer or grant participations to such person or entity or to any other person or entity, with respect to any of the Shares. Paramount represents and warrants that it (a) has been furnished with all information which it deems necessary to evaluate the merits and risks of receipt of the Shares, (b) has had the opportunity to ask questions and receive answers concerning the information received about the Shares and the Company, and (c) has been given the opportunity to obtain any additional information it deems necessary to verify the accuracy of any information obtained concerning the Shares and the Company. Paramount is an “accredited investor” under Regulation D promulgated under the Securities Act of 1933, as amended (the “Securities Act”).

5.2 Paramount hereby agrees that it will in no event sell or distribute all or any part of the Shares unless (a) there is an effective registration statement under the Securities Act, and applicable state and other securities laws covering any such transaction involving the Shares or (b) the Company receives an opinion of Paramount’s legal counsel (which counsel may be Paramount’s internal corporate counsel, and which opinion is reasonable or customary in form and substance) stating that such transaction is exempt from registration or the Company otherwise satisfies itself that such transaction is exempt from registration. The Company shall provide promptly to Paramount all information reasonably requested in connection with preparing such opinion. Paramount understands that the Company has no obligation to register the Shares with the Securities and Exchange Commission (the “SEC”) and has not represented to Paramount that the Company will so register the Shares.

5.3 Paramount confirms that it has been advised, prior to its receipt of the Shares, that neither the offering of the Shares nor any offering materials have been reviewed by any administrator or other governmental entity under the Securities Act or any other applicable securities act.

5.4 The Company represents and warrants that each of the issuance and delivery of the Shares in accordance with the Agreement, as well as the execution and delivery of this Agreement, has been duly authorized by all necessary corporate action on the part of the Company, that all such Shares have been duly reserved for issuance and that the Shares will, upon issuance, be duly and validly issued, fully paid and nonassessable and free and clear of any liens or encumbrances except for restrictions on transfer set forth herein and under applicable securities laws (subject only to the vesting and forfeiture provision in this Agreement). The Company further represents and warrants that, (a) the Company is not, and never has been a “shell company” as defined under Rule 144 of the Securities Act and (b) assuming the accuracy of Section 5.1, the offer, sale and issuance of the Shares to Paramount does not require registration under the Securities Act and is in compliance with applicable federal and state securities laws.

6. Termination of License Agreement; Forfeiture of Unvested Shares

In the event of (a) termination or expiration of the License Agreement due to Paramount’s election to cause an early expiration of the License Agreement pursuant to the proviso in the second sentence of Section 3.B. of the License Agreement or (ii) so long as there has been no acceleration of vesting pursuant to Section 2.2 of this Agreement, immediately following termination or expiration of the License Agreement for any other reason, then no further vesting of Unvested Shares shall take place, all remaining Unvested Shares shall be immediately forfeited by Paramount (or any applicable transferee) as of the date of termination or expiration of the License Agreement without payment of any consideration therefor, and Paramount (or any applicable transferee) shall have no further rights with respect to such Unvested Shares.

7. No Section 83(b) Election for Shares; Independent Tax Advice

Paramount acknowledges that it has not provided, and will not be providing, any services to the Company or to Redbox under the License Agreement or otherwise. As such, Paramount hereby confirms that the Shares are not being transferred in connection with the performance of services within the meaning of Section 83(a) of the Internal Revenue Code of 1986 (the “Code”), and Paramount is not entitled to, and will not make, an election with respect to the Unvested Shares under Section 83(b) of the Code.

PARAMOUNT FURTHER ACKNOWLEDGES THAT THE COMPANY HAS DIRECTED PARAMOUNT TO SEEK INDEPENDENT ADVICE REGARDING THE APPLICABLE PROVISIONS OF THE CODE AND THE INCOME TAX LAWS OF ANY APPLICABLE MUNICIPALITY, STATE OR FOREIGN COUNTRY WHERE PARAMOUNT IS OR MAY BE SUBJECT TO TAX.

Paramount acknowledges that determining the actual tax consequences to Paramount of receiving or disposing of the Shares may be complicated. These tax consequences will depend, in part, on Paramount’s specific situation and may also depend on the resolution of currently uncertain tax law and other variables not within the control of the Company. Paramount is aware that it should consult a competent and independent tax advisor for a full understanding of the specific tax consequences of receiving or disposing of the Shares. Prior to executing this Agreement, Paramount either has consulted with a competent tax advisor independent of the Company to obtain tax advice concerning the Shares in light of its specific situation or has had the opportunity to consult with such a tax advisor but has chosen not to do so.

8. Book Entry Registration of the Shares

The Company will issue the Shares by registering the Shares in book entry form with the Company’s transfer agent in Paramount’s name and the applicable restrictions will be noted in the records of the Company’s transfer agent and in the book entry system. No certificate(s) representing Unvested Shares will be issued until the Shares, or the applicable portion of such Shares, become Vested Shares. Subject to provision by Paramount of any documentation reasonably requested by the Company, upon written request by Paramount the

Company will provide to the transfer agent (and to such other persons as may be reasonably required) such documentation as is reasonably necessary to (a) remove any restrictions under this Agreement with respect to the Unvested Shares that have become Vested Shares or (b) otherwise facilitate a lawful transfer of Unvested Shares or Vested Shares pursuant to the terms and conditions of this Agreement.

9. Stop-Transfer Notices and Restrictive Legends

9.1 Paramount understands and agrees that, in order to ensure compliance with the restrictions and forfeiture conditions referred to in this Agreement, the Company may issue appropriate “stop-transfer” and other instructions to its transfer agent, if any, and that, if the Company transfers its own securities, it may make appropriate notations to the same effect in its own records. The Company will not be required to (a) transfer on its books any Shares that have been sold or transferred in violation of the provisions of this Agreement or (b) treat as the owner of the Shares, or otherwise accord voting, or dividend rights to any transferee to whom the Shares have been transferred in contravention of this Agreement.

9.2 The restrictions noted in the records of the Company’s transfer agent and any certificate or certificates representing the Shares shall bear the following legends in substantially the following form (as well as any other legends required by applicable state and federal corporate securities laws) as reasonably deemed appropriate by the Company:

THE SHARES REPRESENTED BY THIS CERTIFICATE HAVE NOT BEEN REGISTERED UNDER THE SECURITIES ACT OF 1933, AND HAVE BEEN ACQUIRED FOR INVESTMENT AND NOT WITH A VIEW TO, OR IN CONNECTION WITH, THE SALE OR DISTRIBUTION OR OTHER TRANSFER THEREOF. NO SUCH SALE OR DISTRIBUTION MAY BE EFFECTED WITHOUT AN EFFECTIVE REGISTRATION STATEMENT RELATED THERETO OR THE COMPANY’S RECEIPT OF AN OPINION OF TRANSFEROR’S LEGAL COUNSEL STATING THAT SUCH TRANSFER IS EXEMPT FROM REGISTRATION OR THE COMPANY OTHERWISE SATISFIES ITSELF THAT SUCH TRANSFER IS EXEMPT FROM REGISTRATION.

Notwithstanding the foregoing, upon Paramount’s request, promptly following the date that Vested Shares may be sold under Rule 144 without volume restrictions or manner of sale limitations, the Company shall cause its legal counsel to issue a legal opinion to the Company’s transfer agent and to Paramount (which opinion shall be reasonable in form and substance) that any and all certificates representing such Vested Shares shall be issued free of all legends.

10. Rule 144 Reporting

10.1 With a view to making available the benefits of certain rules and regulations of the SEC that will permit the sale of the Vested Shares without registration with the SEC, the Company agrees to:

(a) make and keep public information available, as such terms are understood and defined in Rule 144(c)(i) of the Securities Act, at all times until the one year anniversary from the date on which there are no remaining Unvested Shares held by Paramount under this Agreement;

(b) file with the SEC in a timely manner all reports and other documents required to be filed by the Company under the Securities Exchange Act of 1934, as amended (the “Exchange Act”); and

(c) so long as Paramount owns any Shares, upon request by Paramount, if the Company is not filing reports and other documents under the Exchange Act, the Company will make available other information as required by, and so long as necessary to permit sales of the Shares pursuant to, Rule 144A (including the provision of information to Paramount and prospective purchasers designated by Paramount pursuant to Rule 144A(d)(4)) and, commencing at such time as sales are permitted under Rule 144, Rule 144A, and in any event shall make available (either by mailing a copy thereof, by posting on the Company’s website, or by press release) to Paramount a copy of:

(i) the Company’s annual consolidated financial statements (including at least balance sheets, statements of profit and loss, statements of stockholders’ equity and statements of cash flows) prepared in accordance with generally accepted accounting principles in the United States, no later than 90 days after the end of each fiscal year of the Company; and

(ii) the Company’s quarterly consolidated financial statements (including at least balance sheets, statements of profit and loss, statements of stockholders’ equity and statements of cash flows) prepared in a manner substantially consistent with the preparation of the Company’s annual consolidated financial statements, no later than 45 days after the end of each fiscal quarter of the Company.

10.2 If the Company shall fail for any reason to satisfy the requirements of clause (a) or (b) of this Section 10 (a “Public Information Failure”) then, in addition to Paramount’s other available remedies, the Company shall pay to Paramount, in cash, as partial liquidated damages and not as a penalty, by reason of any such delay in or reduction of its ability to sell the Vested Shares then held by Paramount (or a U.S. affiliate of Paramount), an amount in cash equal to two percent (2.0%) of the aggregate value of the Vested Shares then held by Paramount (or a U.S. affiliate of Paramount) valued at the higher of $31.89 or the average closing price per share of the Company’s Common Stock for the ten full trading days prior to, but not including, the day of the Public Information Failure on the day of a Public Information Failure and on every thirtieth (30^th) day (pro rated for periods totaling less than thirty days) thereafter until the earlier of (i) the date such Public Information Failure is cured and (ii) such time that such public information is no longer required for Paramount to transfer its Vested Shares pursuant to Rule 144. The payments to which Paramount shall be entitled pursuant to this Section 10.2 are referred to herein as “Public Information Failure Payments.” Public Information Failure Payments shall be paid on the earlier of (1) the last day of the calendar month during which such Public Information Failure Payments are

incurred and (2) the third (3^rd) business day after the event or failure giving rise to the Public Information Failure Payments is cured. In the event the Company fails to make Public Information Failure Payments in a timely manner, such Public Information Failure Payments shall bear interest at a rate equal to the lesser of 1.5% per month (prorated for partial months) or the maximum amount allowed by applicable law until paid in full. Nothing herein shall limit Paramount’s right to pursue actual damages for the Public Information Failure, and Paramount shall have the right to pursue all remedies available to it at law or in equity including, without limitation, a decree of specific performance and/or injunctive relief.

11. Tax Withholding

Paramount shall provide such certificates as reasonably requested by the Company to enable the Company to comply with any applicable information reporting or withholding requirements with respect to the Shares, and such certificates may include, among other things, a properly executed IRS Form W-9.

12. General Provisions

12.1 Notices

Whenever any notice is required or permitted hereunder, such notice must be in writing and personally delivered or sent by facsimile or mail. Any notice required or permitted to be delivered hereunder shall be deemed to be delivered on the date on which it is personally delivered or facsimile distributed with verifiable receipt, or, whether actually received or not, on the third business day after it is deposited in the United States mail, certified or registered, postage prepaid, addressed to the party who is to receive it at the address or facsimile number that such party has theretofore specified by written notice delivered in accordance herewith. The Company or Paramount may change, by written notice to the other, the address previously specified for receiving notices. Unless changed pursuant to the terms of this Section, notices delivered to the Company shall be addressed as follows:

and notices delivered to Paramount shall be addressed as follows:

12.2 No Waiver

No waiver of any provision of this Agreement will be valid unless in writing and signed by the party against whom such waiver is sought to be enforced, nor will failure to enforce any right hereunder constitute a continuing waiver of the same or a waiver of any other right hereunder.

12.3 Undertaking

Each party hereby agrees to take whatever additional action and execute whatever additional documents the other party may reasonably deem necessary or advisable in order to carry out or effect one or more of the obligations or restrictions imposed on such party pursuant to the express provisions of this Agreement.

12.4 Entire Contract

This Agreement constitutes the entire agreement between the parties hereto with regard to the subject matter hereof and supersedes all prior oral or written agreements on the subject.

12.5 Successors and Assigns

The provisions of this Agreement will inure to the benefit of, and be binding on, the Company and its successors and assigns and Paramount’s successors and assigns and transferees by operation of law, whether or not any such party will have become a party to this Agreement and agreed in writing to join herein and be bound by the terms and conditions hereof.

12.6 Counterparts

This Agreement may be executed in two or more counterparts, each of which will be deemed an original, but which, upon execution, will constitute one and the same instrument.

12.7 Governing Law

The provisions of this Agreement shall be governed by the laws of the state of Delaware, without giving effect to principles of conflicts of law.

12.8 Confidentiality

The parties acknowledge and agree that the Company may disclose this Agreement in summary tabular form in its next filing on Form 10-Q in to the extent such disclosure is required by the Exchange Act in order to be in compliance with the requirements of Part II, Item 2 of such Form. Except as provided in the preceding sentence, the parties hereto will keep the terms and existence of this Agreement confidential and will not now or hereafter divulge any of this information to any third party except (a) with the prior written consent of the other party; (b) as otherwise may be required by law or legal process or, so long as such disclosure is made pursuant to binding confidentiality obligations, as may be required in connection with profit participants or guild obligations; (c) during the course of litigation, so long as the disclosure of such terms and conditions is restricted in the same manner as is the confidential information of other litigating parties; or (d) in confidence to its affiliates or its, or its affiliates’, legal counsel, accountants, banks, and financing sources and their advisors in connection with complying with or administering its obligations with respect to this Agreement; provided, however, that in (b) and (c) above, to the extent permitted by law, (i) the disclosing party will use all reasonably available legal means to minimize the disclosure to third parties, including, without limitation, seeking a confidential treatment request or protective order whenever appropriate or available; and (ii) the disclosing party will provide the other party with at least ten (10) days’ prior written notice of such disclosure.

[Signature page follows]

IN WITNESS WHEREOF, the parties have executed this Agreement dated as of the date first set forth above.