Adding Foreign Key constraint sucks up memory and causes paging

I'm having a lot of issues adding a simple foreign key constraint to a newly created empty table. Reference table is a tiny one with less than 40 records in it, but it gets referenced quite a bit.

Here's what happens: new table gets created successfully, but when adding a FK constraint, it "thinks" for a really long time and increases CPU load. Memory usage increases, the server starts paging like crazy and becomes unresponsive (connections time out). Cancelling the query does not help. The only thing that works is rebooting the server, which is very costly.

Here's the script I'm trying to run. I'm hoping SQL server gurus can help out. Thx!

USE [my_db]
GO

SET ANSI_NULLS ON
GO

SET QUOTED_IDENTIFIER ON
GO

CREATE TABLE [dbo].[MyNewTable](
    [Column1ID] [int] NOT NULL,
    [Column2ID] [int] NOT NULL
) ON [PRIMARY]

GO

ALTER TABLE [dbo].[MyNewTable]  WITH CHECK ADD  CONSTRAINT [FK_MyNewTable_Column1ID] FOREIGN KEY([Column1ID])
REFERENCES [dbo].[ReferenceTable] ([Column1ID])
ON UPDATE CASCADE
ON DELETE CASCADE
GO

ALTER TABLE [dbo].[MyNewTable] CHECK CONSTRAINT [FK_MyNewTable_Column1ID]
GO

EDIT: ReferenceTable is a small table that looks something like this:

[Column1ID] [int] IDENTITY(1,1) NOT NULL,
[TxtCol1] [varchar](50) NOT NULL,
[TxtCol2] [varchar](50) NOT NULL,
[TxtCol3] [varchar](200) NOT NULL,
[TxtCol4] [nvarchar](2000) NOT NULL,
[TxtCol5] [varchar](200) NOT NULL,
[BitCol1] [bit] NOT NULL,
[TxtCol6] [varchar](200) NOT NULL,
[NumCol1] [smallint] NOT NULL,
[ExternalColumnId] [int] NOT NULL,
[NumCol2] [int] NOT NULL

Column1ID is referenced a lot by other tables (FK's). ExternalColumnId is a FK to another table. The problem happens during one of the ALTER TABLE calls. Unfortunately both of those were run together, so I'm unable to say which one caused it.

EDIT: Once the DB goes into "thinking" mode, it's possible to bring it back up by switching it to single mode and then back to multi user mode. It is much better than rebooting the server but still unacceptable.