Shade
Monster Junkie
Perhaps we're going about this the wrong way. The SRD Octopus does not have multiple tentacle attacks like their giant versions, just a single attack with its arms. The SRD Squid does the same, and that's Medium sized like the Deepwater Octopus. We could just give it a single "Arms" attack with its tentacles in the same fashion.
That only works since their arms deal no actual damage. It's a bit like the "attach" damage for some creatures that attack only to latch on, but deal no damage.
EDIT: I have a feeling the debate over this is going to be as long as that over Houyhnhnm Hoof damage.
Weeps profusely.

The original only had 6 tentacles (should we change that in our writeup?) presumably to keep the other two free for manipulating things and didn't get a Str bonus. Taking 1d6 tentacles at 1d2 each gives an average constrict damage of 3.5*1.5=5.25. 1d6+1 gives an average of 4.5, which isn't that far off. And that's assuming that you get lots of tentacles attached as much as just 1 or 2. I just don't think we should compare constrict by adding in Str for each tentacle, since that's not how constrict generally works in 3.X. We've done some exceptional constricts in the past, I think, but those were for more exceptional monsters, too.
I like 1d6+1 for a creature of its power level.
I do think we should add the shortspear to the attack line as a possibility.
Agreed.