Does the size of the primary key contribute to table size?
SHORT ANSWER

It is really the other way around : The size of the table contributes to the size of the primary key. Therefore, YES it was to be expected.

LONG ANSWER

The Primary Key resides within gen_clust_index, a.k.a. the Clustered Index.

According to the MySQL Documentation on the Clustered Index


  How the Clustered Index Speeds Up Queries
  
  Accessing a row through the clustered index is fast because the row
  data is on the same page where the index search leads. If a table is
  large, the clustered index architecture often saves a disk I/O
  operation when compared to storage organizations that store row data
  using a different page from the index record. (For example, MyISAM
  uses one file for data rows and another for index records.)


From this description, the InnoDB Storage Engine has each row sits inside the Clustered Index.

In light of this, two questions need answering:


Why does dropping the PRIMARY KEY not shrink the Clustered Index?
Why does OPTIMIZE TABLE not shrink the Clustered Index?


The answer to both questions is but one. The MySQL Documentation on the Clustered Index says:


  If the table has no PRIMARY KEY or suitable UNIQUE index, InnoDB
  internally generates a hidden clustered index on a synthetic column
  containing row ID values. The rows are ordered by the ID that InnoDB
  assigns to the rows in such a table. The row ID is a 6-byte field that
  increases monotonically as new rows are inserted. Thus, the rows
  ordered by the row ID are physically in insertion order.


Think about it : OPTIMIZE TABLE is rendered ineffective since you made no attempt to delete any rows. Since you did not delete any rows, all the space occupied by rows will still sit within the Clustered Index. You merely traded-in one key (your Primary Key) for another (the 6-byte row ID).

What are the ways to shrink the Clustered Index ?

I have one of three(3) techniques you may need to do

TECHNIQUE #1 : Reducing the Length of your Columns


shrink INTs to SMALLINTs or TINYINTs
shrink VARCHAR(255) to VARCHAR(128)


TECHNIQUE #2 : Delete Old Rows


Look for rows with really old timestamps, then either


Delete the Old Rows
Archive the Old Rows in another table



TECHNIQUE #3 : Dropping Columns From the Table


This is true in theory
Nobody wants to lose data in the Process
Archive the Table Before Dropping Columns


CAVEAT

Before you apply one of these three(3) techniques, please backup your table.

EPILOGUE

Once you have applied one of these three(3) techniques, then you can do one of the following in order to shrink the Clustered Index (for let's say, mydb.mytable):


OPTIMIZE TABLE mydb.mytable;
ALTER TABLE mydb.mytable ENGINE=InnoDB;


Give it a Try !!!

UPDATE 2013-06-17 07:34 EDT

Here is your last comment


  So if the original primary key was greater than 6-bytes wouldn't I expect to see a decrease in the clustered index size?


Even if PRIMARY KEY is now CHAR(255), each row sits inside the Clustered Index. Each page in InnoDB is 16K. The 6-byte row ID (which InnoDB still uses internally anyway) is still embedded within the same pages. Dropping the PRIMARY KEY is more of a logical dropping than a physical one. That's why I said earlier 


  You merely traded-in one key (your Primary Key) for another (the 6-byte row ID)


The physical act of dropping the PRIMARY KEY may entail running around to every row in tombstoning (flagging) each row not to use some internal column combination for the PRIMARY KEY but to revert back to the row ID. That would hardly change the usage of a 16K InnoDB Page, regardless of the Row Length Being Long (which may allow for a few rows within the Page) or Short (which may allow for many more rows within the Page).

Running OPTIMIZE TABLE to shrink it still won't make any noticeable change because the flagging mechanism still exists for the Clustered Index. The exact same number of rows, given the average length of your rows in the table, keeps the Clustered Index the same size.

Look over the three techniques I mentioned before and the MySQL Documentation on the Clustered Index. Given the number of rows in the table and your current table definition, if you cannot reduce column sizes, remove columns, delete rows and archive them elsewhere, then there is nothing you can do to shrink the table.