Storyboardには、UIGestureRecognizerも配置できますが、UITableViewCellのPrototypeにOutletを紐付けるとビルド時にエラーとなります。

error: Illegal Configuration: Gesture recognizers cannot be used on prototype objects.

エラー内容によると、ジェスチャはStoryboardのプロトタイプオブジェクトでは使えないようです。
コードで何とかするしかないですが、UITableViewCellは再利用を前提としていて、初めてデキューされたオブジェクトだけにジェスチャを紐付けするように工夫する必要があります。

static NSString *CellIdentifier = @"Cell";
UITableViewCell *cell = [tableView dequeueReusableCellWithIdentifier:CellIdentifier forIndexPath:indexPath];
BOOL found = NO;
for (UIGestureRecognizer *gesture in cell.gestureRecognizers) {
    if ([gesture isMemberOfClass:[UILongPressGestureRecognizer class]]) {
        found = YES;
        break;
    }
}
if (!found) {
    UILongPressGestureRecognizer *gesture = [[UILongPressGestureRecognizer alloc] initWithTarget:self action:@selector(handleLongPressGesture:)];
    [cell addGestureRecognizer:gesture];
}

ちなみに、if (!found)の判定をなくして、cell.gestureRecognizersにジェスチャが複数回登録された場合どうなるかを確認したところ、handleLongPressGesture:が実行されるのは1回だけでした。
複数回登録したとしても動作上問題は無さそうですが、もしかしたら弊害があるかもしれないので、特に理由がなければ登録は1回だけにしておいたほうがいいと思います。
(XCode 4.6.3 + iOS 6.1 SDK + iPhone 6.1 Simulatorで確認)