Reproduced with
LibreOffice 3.3.2 RC2 (1:3.3.0-1lucid1) - Ubuntu 10.04 x86 Linux 2.6.32-28-generic Russian UI

Per conversation in #libreoffice:

01:48 < mikemol> My assumption about how spreadsheet apps work is that they don't uniquely track cell contents until they're needed.
01:51 < mikemol> So if one does an operation like "paste to column", it could be assumed that the column extends to infinity. The sane option, to me, would be treat the paste as a default cell value 
                 for any new cells created later in that column.
01:52 < mikemol> If a cell isn't viewed or printed, there's no need to precalculate anything about it. (Obviously, exporting or printing raise interesting questions.)
01:53 < mikemol> I ran across that while trying to apply some conditional formatting to a full column.
02:00 < szal> Excel 2007 will fill the column w/ the respective relative value (e.g., when pasting "=B1" from A1 to column C, it will show "=D1", "=D2", etc.)
02:01 < szal> mikemol: so perhaps you should modify your bug putting that in as "expected result"

So, expected result:

LO should defer calculating the contents for cells not otherwise made unique. As a result, a paste operation such as the one described would result in something like a template or default cell value for the column, for when cells are created. (Or for when cells are queried).

Additional information:

These analogous steps (testing for behavior of pasting to rows) do not hang LO:

In cell A1, enter the formula: =A2
Copy cell A1
Click the header for row 3
Paste

(Calc does not hang)

Reproduced with LibreOffice 3.5.2.2 
Build ID: 281b639-6baa1d3-ef66a77-d866f25-f36d45f

On MACOS 10.7 so NOT Windows only
No localization applied, from fresh install over LO 3.4.

Also : steps in Comment 3 from Michael Mol DOES hang LO in my case.

Generally my experience is that pasting a formula to a whole column or more results in very long treatment time or a hang.

Suggested fix : 
break the process of pasting to many cells (>1000) in these steps :
- time a sample of the process (100 cells)
- evaluate the full treatment time (of 1M cells)
- if estimated time is more than UI acceptable standards : ask confirmation before proceeding or cancel treatment.
Alternatively : Treat as a long process with a progress bar and a cancel button.

(In reply to comment #0)
> In column A1, enter the formula: =B1
> 
> Copy cell A1
> 
> Click header for column C.
> 
> Paste.
> 
> Calc is now hung.

I can not reproduce the problem with version 3.6build 304 (SUSE) on openSUSE12.3, nor on version 4.0.4 on Windows.
It takes some time (in my case 2 to 10 seconds, depending on the OS/machine), as can be expected, but LibreOffice does not hang.

Michael, I have taken the liberty to change the status to fixed in order to minimise the number of open bugreports that require no further action. Please reopen if the problem is not solved for you.

It still hangs, but not for an unbearable amount of time on this system (Intel B940 @ 2.00 GHz).

Could be better, but it's good enough for me...

Ah, I should note that my latest test is with 4.0.4.2 on Gentoo amd64.

[I] app-office/libreoffice
     Available versions:  3.6.6.2 **3.6.9999 4.0.4.2 **4.0.9999 ~4.1.0.1 **4.1.9999 **9999-r2 {{aqua binfilter binfilterdebug bluetooth +branding +cups dbus debug eds elibc_FreeBSD gnome gstreamer +gtk gtk3 java jemalloc kde libreoffice_extensions_nlpsolver libreoffice_extensions_pdfimport libreoffice_extensions_presenter-console libreoffice_extensions_presenter-minimizer libreoffice_extensions_scripting-beanshell libreoffice_extensions_scripting-javascript libreoffice_extensions_wiki-publisher mysql odk opengl postgres python_single_target_python2_5 python_single_target_python2_6 python_single_target_python2_7 python_single_target_python3_3 python_targets_python2_5 python_targets_python2_6 python_targets_python2_7 python_targets_python3_3 telepathy test +vba +webdav}}
     Installed versions:  4.0.4.2(05:11:33 AM 07/04/2013)(bluetooth branding cups dbus gstreamer gtk libreoffice_extensions_presenter-minimizer opengl python_single_target_python2_7 python_targets_python2_7 vba webdav -aqua -debug -eds -elibc_FreeBSD -gnome -java -jemalloc -kde -libreoffice_extensions_nlpsolver -libreoffice_extensions_scripting-beanshell -libreoffice_extensions_scripting-javascript -libreoffice_extensions_wiki-publisher -mysql -odk -postgres -python_single_target_python3_3 -python_targets_python3_3 -telepathy -test)
     Homepage:            http://www.libreoffice.org
     Description:         LibreOffice, a full office productivity suite.